Using Confidence Bounds for Exploitation-Exploration Trade-offs

P. Auer

article2003JMLR2,135 citations

Real-world automated decision systems must continuously balance exploiting known high-performing options to maximize immediate rewards with exploring uncertain options to discover better strategies. This exploration-exploitation tension is especially critical in non-stationary and complex environments, such as internet advertising, dynamic pricing, and game-theoretic scenarios, where reward structures change over time or depend on rich contextual features. Traditional approaches often fail to provide reliable performance guarantees in these demanding settings, leaving decision-makers exposed to high-variance outcomes.

The article establishes a rigorous mathematical framework using statistical confidence bounds to solve the exploration-exploitation trade-off across two complex decision models: the adversarial bandit problem with shifting targets and associative reinforcement learning with linear value functions.

To address these challenges, the article develops two tailored algorithmic frameworks and evaluates them through mathematical performance proofs and concentration analyses. For the shifting adversarial bandit model, the article introduces an algorithm that applies an exponential weighting scheme combined with deliberate over-estimation via confidence bounds to manage the algorithm's internal randomization. For associative reinforcement learning, where expected rewards depend linearly on multi-dimensional feature vectors, the article designs a confidence-based linear regression approach governed by a multi-stage master framework to ensure data independence across decision steps.

The core findings demonstrate significant, provable improvements in learning performance. First, for adversarial bandits with shifting targets, the new algorithm achieves a regret rate that grows roughly with the square root of both the number of trials and the number of shifts with high probability, matching the theoretical optimal lower bound and eliminating the severe outcome variance of previous expected-value methods. Second, for associative reinforcement learning, the algorithm substantially improves cumulative regret scaling from a three-quarter power rate down to a square-root rate with high probability, significantly reducing long-term performance loss. Third, the analysis proves that statistical confidence intervals effectively guide exploration both when addressing external environmental noise and when compensating for internal algorithmic randomization.

These findings provide strong operational value for automated decision systems. They show that organizations can deploy adaptive algorithms that rapidly adjust to changing environments without risking catastrophic performance dips. By replacing expected-value estimates with confidence bounds that explicitly incorporate uncertainty, system performance becomes far more predictable and robust, lowering operational risk in high-stakes environments.

Organizations developing automated recommendation engines, ad-scheduling platforms, or adaptive allocation tools should adopt confidence-bound exploration mechanisms over ad-hoc tuning strategies. Practitioners should proceed by evaluating the linear confidence algorithms in domain-specific simulation pipelines and fine-tuning constant parameters, which are critical to performance in production settings. Further research should focus on empirical benchmarking and refining these constants for specific real-world applications.

Confidence in these mathematical bounds is high due to comprehensive proofs, but certain limitations apply. The reinforcement learning framework assumes expected rewards follow a linear relationship with input features and that immediate actions do not alter future environmental states. Decision-makers should account for these boundary conditions when applying these algorithms to more complex, multi-step environments.

adaptive algorithms decision models decision systems Algorithm Con Dence Bounds

Auer (2003).pdf

Paper: Finite-time Analysis of the Multiarmed Bandit Problem, Peter Auer et al. (2002). It introduces foundational upper confidence bound algorithms and finite-time logarithmic regret analysis that the source adapts to linear and non-stationary bandit settings.
Paper: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund et al. (1997). It establishes the multiplicative weight-updating Hedge algorithm and adversarial regret analysis that underpin the source's exponential weighting approach for shifting bandit targets.
Paper: Stability and Generalization, Olivier Bousquet et al. (2002). It provides the sensitivity and concentration inequality techniques essential for understanding the source's high-probability statistical confidence bound proofs.
Paper: Active Learning with Statistical Models, D. Cohn et al. (1996). It derives variance-minimizing query selection rules in linear regression models that directly motivate using linear confidence bounds to guide sequential exploration.
Paper: Reinforcement Learning: A Survey, Leslie Pack Kaelbling et al. (1996). It offers the classic framing of the exploration-exploitation dilemma across multi-armed bandits and reinforcement learning that the source formalizes mathematically.

Paper: A contextual-bandit approach to personalized news article recommendation, Lihong Li et al. (2010). It builds directly upon the source's confidence-bound linear bandit framework to develop LinUCB for industrial personalized recommendation systems.
Paper: Improved Algorithms for Linear Stochastic Bandits, Yasin Abbasi-Yadkori et al. (2011). It significantly refines the source's linear bandit bounds by introducing self-normalized vector-valued martingales that remove master-framework independence assumptions.
Paper: An Empirical Evaluation of Thompson Sampling, Olivier Chapelle et al. (2011). It compares empirical Bayesian alternatives to the deterministic upper confidence bound strategies analyzed in the source across large-scale recommendation tasks.
Paper: Counterfactual Risk Minimization: Learning from Logged Bandit Feedback, Adith Swaminathan et al. (2015). It extends confidence-bound exploration principles to batch offline learning from logged bandit feedback using variance-regularized policy optimization.
Paper: Time-uniform, nonparametric, nonasymptotic confidence sequences, Steven R. Howard et al. (2021). It generalizes time-uniform statistical bounds and non-asymptotic confidence sequences using modern martingale concentration techniques.

1. Introduction
2. Upper Confidence Bounds for the Random Bandit Problem
3. The Adversarial Bandit Problem with Shifts
3.1 The Algorithm for the Adversarial Bandit Problem with Shifting
3.2 Proof of Theorem 2
4. Associative Reinforcement Learning with Linear Value Functions
4.1 An Algorithm for Associative Reinforcement Learning with Linear Value Functions
4.2 Analysis of Algorithm LinRel
4.3 The Master Algorithm
5. Conclusion
Acknowledgments
Appendix A. Proof of Lemmas 11 and 12
References

Knowls

Knowl 1 — High-Probability Regret Bound for SupLinRel in Linear Contextual Bandits
theoretical result
For the associative reinforcement learning problem with linear value functions over $T$ trials with $K$ actions and feature vectors $z_i(t) \in \mathbb{R}^d$ satisfying $\|z_i(t)\| \le 1$ and an unknown parameter vector $f \in \mathbb{R}^d$ satisfying $\|f\| \le 1$ with independent rewards $x_i(t) \in [0, 1]$ having mean $\mathbb{E}[x_i(t)] = f \cdot z_i(t)$ , the ${\mathchoice{\text{S{\scriptsize UP}L{\scriptsize IN}R{\scriptsize EL}}}{\text{S{\scriptsize UP}L{\scriptsize IN}R{\scriptsize EL}}}{\text{S{\scriptscriptstyle UP}L{\scriptscriptstyle IN}R{\scriptscriptstyle EL}}}{\text{SUPLINREL}}}$ algorithm run with confidence parameter $\delta / (1 + \ln T)$ achieves a high-probability regret bound against the optimal per-trial action $i^*(t) = \arg\max_{i \in \{1,\dots,K\}} f \cdot z_i(t)$ .

With probability at least $1 - \delta$ , the cumulative regret $B(T) = \sum_{t=1}^T x_{i^*(t)}(t) - \sum_{t=1}^T x_{i(t)}(t)$ satisfies:

$B(T) \le 44 \left(1 + \ln(2KT \ln T)\right)^{3/2} \sqrt{Td} + 2\sqrt{T} = \tilde{O}\left(\sqrt{Td}\right)$

This improves the previously known expected regret bound of $\tilde{O}(T^{3/4})$ for linear associative reinforcement learning to $\tilde{O}(\sqrt{Td})$ with high probability.
Knowl 2 — SupLinRel Algorithm
algorithm
${\mathchoice{\text{S{\scriptsize UP}L{\scriptsize IN}R{\scriptsize EL}}}{\text{S{\scriptsize UP}L{\scriptsize IN}R{\scriptsize EL}}}{\text{S{\scriptscriptstyle UP}L{\scriptscriptstyle IN}R{\scriptscriptstyle EL}}}{\text{SUPLINREL}}}$ is a master algorithm for associative reinforcement learning with linear value functions (linear contextual bandits) that coordinates multiple instances of the ${\mathchoice{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptscriptstyle IN}R{\scriptscriptstyle EL}}}{\text{LINREL}}}$ confidence bound mechanism across $S = \lfloor\ln T\rfloor$ filtering stages. This multi-stage filtering ensures conditional statistical independence of reward samples while maintaining an $\tilde{O}(\sqrt{Td})$ cumulative regret guarantee.

In each trial $t \in \{1,\dots,T\}$ , the algorithm receives $K$ context vectors $z_1(t), \dots, z_K(t) \in \mathbb{R}^d$ . It maintains $S$ disjoint index sets $\Psi^{(1)},\dots,\Psi^{(S)} \subseteq \{1,\dots,t-1\}$ , each tracking trials assigned to exploration at stage $s$ . The candidate arm set is initialized to $A_1 = \{1,\dots,K\}$ . At stage $s$ , the algorithm queries ${\mathchoice{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptscriptstyle IN}R{\scriptscriptstyle EL}}}{\text{LINREL}}}$ on history $\Psi^{(s)}$ to obtain upper confidence bounds $\text{ucb}_i^{(s)}(t)$ and confidence widths $\text{width}_i^{(s)}(t)$ for candidate arms $i \in A_s$ :
1. If any arm has $\text{width}_i^{(s)}(t) > 2^{-s}$ , it selects that arm, observes its reward, adds trial $t$ to $\Psi^{(s)}$ , and completes the trial.
2. Else if all arms in $A_s$ have $\text{width}_i^{(s)}(t) \le 1/\sqrt{T}$ , it selects the arm maximizing $\text{ucb}_i^{(s)}(t)$ without adding $t$ to any stage history.
3. Else if all arms in $A_s$ have $\text{width}_i^{(s)}(t) \le 2^{-s}$ , it eliminates provably suboptimal arms by updating $A_{s+1} = \{i \in A_s : \text{ucb}_i^{(s)}(t) \ge \max_{j \in A_s} \text{ucb}_j^{(s)}(t) - 2 \cdot 2^{-s}\}$ and advances to stage $s+1$ .
Input: Horizon $T$ , arms $K$ , dimension $d$ , confidence parameter $\delta \in (0, 1]$
Initialize $S \leftarrow \lfloor \ln T \rfloor$
Initialize $\Psi^{(1)} \leftarrow \emptyset, \dots, \Psi^{(S)} \leftarrow \emptyset$
for $t = 1$ to $T$ do
    Receive feature vectors $z_1(t), \dots, z_K(t) \in \mathbb{R}^d$
    Set $A_1 \leftarrow \{1, \dots, K\}$ and $s \leftarrow 1$
    repeat
        Compute $\text{ucb}_i^{(s)}(t)$ and $\text{width}_i^{(s)}(t)$ for all $i \in A_s$ using ${\mathchoice{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptscriptstyle IN}R{\scriptscriptstyle EL}}}{\text{LINREL}}}$ on index set $\Psi^{(s)}$ with parameter $\delta$
        if exists $i \in A_s$ such that $\text{width}_i^{(s)}(t) > 2^{-s}$ then
            Choose $i(t) \leftarrow i$
             $\Psi^{(s)} \leftarrow \Psi^{(s)} \cup \{t\}$
            Observe reward $x_{i(t)}(t) \in [0, 1]$
            break
        else if for all $i \in A_s$ , $\text{width}_i^{(s)}(t) \le 1/\sqrt{T}$ then
            Choose $i(t) \leftarrow \arg\max_{i \in A_s} \text{ucb}_i^{(s)}(t)$
            Observe reward $x_{i(t)}(t) \in [0, 1]$
            break
        else if for all $i \in A_s$ , $\text{width}_i^{(s)}(t) \le 2^{-s}$ then
             $A_{s+1} \leftarrow \{i \in A_s : \text{ucb}_i^{(s)}(t) \ge \max_{j \in A_s} \text{ucb}_j^{(s)}(t) - 2 \cdot 2^{-s}\}$
             $s \leftarrow s + 1$
        end if
    until an action $i(t)$ is chosen
end for
Knowl 3 — LinRel Confidence Bound Algorithm
algorithm
${\mathchoice{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptscriptstyle IN}R{\scriptscriptstyle EL}}}{\text{LINREL}}}$ is a linear confidence bound procedure used to construct upper confidence bounds (UCBs) for linear contextual bandits. Given an active subset of previous trials $\Psi \subseteq \{1,\dots,t-1\}$ , the selected context matrix $Z = [z_{i(\tau)}(\tau)]_{\tau \in \Psi} \in \mathbb{R}^{d \times |\Psi|}$ , the corresponding observed rewards $x = (x_{i(\tau)}(\tau))_{\tau \in \Psi} \in [0, 1]^{1 \times |\Psi|}$ , and candidate feature vectors $z_1(t), \dots, z_K(t) \in \mathbb{R}^{d \times 1}$ , ${\mathchoice{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptsize IN}R{\scriptsize EL}}}{\text{L{\scriptscriptstyle IN}R{\scriptscriptstyle EL}}}{\text{LINREL}}}$ computes estimated expected rewards and confidence widths via spectral decomposition.

The algorithm computes the eigendecomposition:

$Z Z^\top = U^\top \Delta(\lambda_1, \dots, \lambda_d) U$

where $\lambda_1 \ge \dots \ge \lambda_k \ge 1 > \lambda_{k+1} \ge \dots \ge \lambda_d \ge 0$ and $U^\top U = I_d$ .

For each arm $i$ , the rotated vector $\tilde{z}_i = U z_i$ is partitioned into its large-eigenvalue component $\tilde{u}_i = (\tilde{z}_{i,1}, \dots, \tilde{z}_{i,k}, 0, \dots, 0)^\top$ and small-eigenvalue component $\tilde{v}_i = (0, \dots, 0, \tilde{z}_{i,k+1}, \dots, \tilde{z}_{i,d})^\top$ . The reconstruction coefficient vector $a_i(t) \in \mathbb{R}^{1 \times |\Psi|}$ is defined by:

$a_i(t) = \tilde{u}_i^\top \Delta\left(\frac{1}{\lambda_1}, \dots, \frac{1}{\lambda_k}, 0, \dots, 0\right) U Z$

The confidence interval width and upper confidence bound for arm $i$ are:

$\text{width}_i(t) = \|a_i(t)\| \sqrt{\ln(2TK/\delta)} + \|\tilde{v}_i\|$

$\text{ucb}_i(t) = x a_i(t)^\top + \text{width}_i(t)$
Input: Index subset $\Psi$ , matrix $Z \in \mathbb{R}^{d \times |\Psi|}$ , reward vector $x \in [0, 1]^{1 \times |\Psi|}$ , candidate vectors $\{z_i\}_{i \in A}$ , parameters $T, K, \delta$
Compute spectral decomposition $Z Z^\top = U^\top \text{diag}(\lambda_1, \dots, \lambda_d) U$ with $\lambda_1 \ge \dots \ge \lambda_k \ge 1 > \lambda_{k+1} \ge \dots \ge \lambda_d$
for each arm $i \in A$ do
     $\tilde{z}_i \leftarrow U z_i$
     $\tilde{u}_i \leftarrow (\tilde{z}_{i,1}, \dots, \tilde{z}_{i,k}, 0, \dots, 0)^\top$
     $\tilde{v}_i \leftarrow (0, \dots, 0, \tilde{z}_{i,k+1}, \dots, \tilde{z}_{i,d})^\top$
     $a_i \leftarrow \tilde{u}_i^\top \text{diag}(1/\lambda_1, \dots, 1/\lambda_k, 0, \dots, 0) U Z$
     $\text{width}_i \leftarrow \|a_i\| \sqrt{\ln(2TK/\delta)} + \|\tilde{v}_i\|$
     $\text{ucb}_i \leftarrow x a_i^\top + \text{width}_i$
end for
Output: $\{\text{ucb}_i\}_{i \in A}$ and $\{\text{width}_i\}_{i \in A}$
Knowl 4 — High-Probability Tracking Regret Bound for ShiftBand
theoretical result
For the adversarial multi-armed bandit problem with shifting targets over $T$ trials, $K$ arms, rewards $x_i(t) \in [0, 1]$ , and at most $S$ arbitrary shifts in the optimal arm identity, the ${\mathchoice{\text{S{\scriptsize HIFT}B{\scriptsize AND}}}{\text{S{\scriptsize HIFT}B{\scriptsize AND}}}{\text{S{\scriptscriptstyle HIFT}B{\scriptscriptstyle AND}}}{\text{SHIFTBAND}}}$ algorithm achieves a high-probability regret bound against the best piecewise constant arm schedule with $S$ segments.

If $T \ge 144 KS \ln(TK/\delta)$ and ${\mathchoice{\text{S{\scriptsize HIFT}B{\scriptsize AND}}}{\text{S{\scriptsize HIFT}B{\scriptsize AND}}}{\text{S{\scriptscriptstyle HIFT}B{\scriptscriptstyle AND}}}{\text{SHIFTBAND}}}$ is executed with parameters:

$\alpha = 2\sqrt{\ln\left(\frac{T^3 K}{\delta}\right)}, \quad \beta = \frac{1}{T}, \quad \eta = \sqrt{\frac{S \ln(TK)}{TK}}, \quad \gamma = 2K\eta$

then with probability at least $1 - \delta$ , the tracking regret satisfies:

$R_S(T) = \max_{0=t_0 < t_1 < \dots < t_S = T} \left(\sum_{s=1}^S \max_{i \in \{1,\dots,K\}} \sum_{t=t_{s-1}+1}^{t_s} x_i(t)\right) - \sum_{t=1}^T x_{i(t)}(t) \le 11 \sqrt{TKS \ln\left(\frac{T^3 K}{\delta}\right)}$

If the true shift count $S$ is unknown and the algorithm is run with a parameter $S_0$ under $T \ge 144 KS_0 \ln(TK/\delta)$ and $\eta = \sqrt{\frac{S_0 \ln(TK)}{TK}}$ , the regret is bounded with probability at least $1-\delta$ by:

$R_S(T) \le \left(8\sqrt{S_0} + 3\frac{S}{\sqrt{S_0}}\right) \sqrt{TK \ln\left(\frac{T^3 K}{\delta}\right)}$
Knowl 5 — ShiftBand Algorithm
algorithm
${\mathchoice{\text{S{\scriptsize HIFT}B{\scriptsize AND}}}{\text{S{\scriptsize HIFT}B{\scriptsize AND}}}{\text{S{\scriptscriptstyle HIFT}B{\scriptscriptstyle AND}}}{\text{SHIFTBAND}}}$ is an online algorithm for the adversarial multi-armed bandit problem with shifting targets. It combines exponential weighting with an upper-confidence-bound exploration bonus and a weight-mixing floor $\beta W(t)/K$ to rapidly adapt to non-stationary payoff shifts while establishing high-probability regret guarantees.

At each trial $t \in \{1,\dots,T\}$ , given weights $w_1(t), \dots, w_K(t)$ , total weight $W(t) = \sum_{i=1}^K w_i(t)$ , and exploration rate $\gamma$ , the algorithm chooses an arm $i(t)$ sampled from distribution $p(t) = (1-\gamma) \frac{w(t)}{W(t)} + \frac{\gamma}{K} \mathbf{1}$ . Upon receiving reward $x_{i(t)}(t) \in [0, 1]$ , it forms the unbiased reward estimate $\hat{x}_i(t) = \frac{x_i(t)}{p_i(t)} \mathbb{I}\{i = i(t)\}$ and adds an optimistic exploration bias $\frac{\alpha}{p_i(t)\sqrt{TK/S}}$ to update weights.
Input: Horizon $T$ , segment bound $S$ , arm count $K$ , parameters $\alpha, \beta, \eta > 0, \gamma \in (0, 1]$
Initialize $w_i(1) \leftarrow 1$ for all $i \in \{1, \dots, K\}$
for $t = 1$ to $T$ do
     $W(t) \leftarrow \sum_{i=1}^K w_i(t)$
    for $i = 1$ to $K$ do
         $p_i(t) \leftarrow (1 - \gamma) \frac{w_i(t)}{W(t)} + \frac{\gamma}{K}$
    end for
    Draw arm $i(t) \in \{1, \dots, K\}$ according to probability distribution $p(t)$
    Observe reward $x_{i(t)}(t) \in [0, 1]$
    for $i = 1$ to $K$ do
        if $i = i(t)$ then
             $\hat{x}_i(t) \leftarrow \frac{x_{i(t)}(t)}{p_i(t)}$
        else
             $\hat{x}_i(t) \leftarrow 0$
        end if
         $w_i(t+1) \leftarrow w_i(t) \exp\left( \eta \left( \hat{x}_i(t) + \frac{\alpha}{p_i(t) \sqrt{TK/S}} \right) \right) + \frac{\beta}{K} W(t)$
    end for
end for
Knowl 6 — Associative Reinforcement Learning with Linear Value Functions
definition
The associative reinforcement learning framework with linear value functions (also known as the linear contextual bandit problem) is an online decision-making setting operating over $T$ discrete trials. In each trial $t \in \{1,\dots,T\}$ :
1. The environment reveals $K$ feature vectors $z_1(t), \dots, z_K(t) \in \mathbb{R}^d$ , where $\|z_i(t)\| \le 1$ for all $i \in \{1,\dots,K\}$ .
2. The learner chooses an action $i(t) \in \{1,\dots,K\}$ .
3. The learner observes an independent random reward $x_{i(t)}(t) \in [0, 1]$ generated according to an unknown fixed weight vector $f \in \mathbb{R}^d$ with $\|f\| \le 1$ , satisfying:
$\mathbb{E}[x_i(t) \mid z_i(t)] = f \cdot z_i(t) \quad \text{for all } i \in \{1,\dots,K\}$

The benchmark optimal policy selects action $i^*(t) = \arg\max_{i \in \{1,\dots,K\}} f \cdot z_i(t)$ in each trial $t$ , and the cumulative regret of the learner over $T$ trials is defined as:

$B(T) = \sum_{t=1}^T x_{i^*(t)}(t) - \sum_{t=1}^T x_{i(t)}(t)$
Knowl 7 — Adversarial Bandit Problem with Shifting Targets
definition
The adversarial multi-armed bandit problem with shifting targets is a non-stationary online learning formulation where an adversary selects reward sequences $x_i(t) \in [0, 1]$ for $K$ arms over $T$ trials without statistical assumptions. In each trial $t \in \{1,\dots,T\}$ , the learner selects an arm $i(t) \in \{1,\dots,K\}$ and observes only the reward of the chosen arm $x_{i(t)}(t)$ .

Performance is evaluated against the best sequence of actions partitioned into $S$ contiguous segments $0 = t_0 < t_1 < \dots < t_S = T$ , where a fixed arm is chosen within each segment. The tracking regret against the optimal $S$ -segment schedule is defined as:

$R_S(T) = \max_{0=t_0 < t_1 < \dots < t_S = T} \left(\sum_{s=1}^S \max_{i \in \{1,\dots,K\}} \sum_{t=t_{s-1}+1}^{t_s} x_i(t)\right) - \sum_{t=1}^T x_{i(t)}(t)$
Knowl 8 — Cumulative Bounds on Reconstruction Norms and Residuals via Spectral Potential
theoretical result
In the spectral confidence analysis for linear contextual bandits with feature matrix $Z(t) = [z_{i(\tau)}(\tau)]_{\tau \in \Psi(t)} \in \mathbb{R}^{d \times |\Psi(t)|}$ satisfying $\|z_i(t)\| \le 1$ , let $a_{i(t)}(t)$ be the reconstruction coefficient vector for the top eigenspace of $Z(t) Z(t)^\top$ (eigenvalues $\lambda_j(t) \ge 1$ ) and let $\tilde{v}_{i(t)}(t)$ be the orthogonal projection onto the small eigenspace (eigenvalues $\lambda_j(t) < 1$ ).

When trials are sequentially added to the active set $\Psi(T+1) \subseteq \{1,\dots,T\}$ , the cumulative norms of the reconstruction weights and the residual vectors are bounded as:

$\sum_{t \in \Psi(T+1)} \|a_{i(t)}(t)\| \le 2\sqrt{5 d |\Psi(T+1)| \ln |\Psi(T+1)|}$

$\sum_{t \in \Psi(T+1)} \|\tilde{v}_{i(t)}(t)\| \le 5\sqrt{d |\Psi(T+1)|}$

These bounds establish that the growth in eigenvalues of $Z(t) Z(t)^\top$ acts as a potential function controlling the cumulative uncertainty of linear reward estimates.

Coverage note — None omitted; all core models, algorithms, and theoretical regret bounds for both shifting adversarial bandits and linear associative reinforcement learning are fully covered.

References

1.N. Abe and P. M. Long. Associative reinforcement learning using linear probabilistic concepts. In Proc. 16th International Conf. on Machine Learning, pages 3–11. Morgan Kaufmann, San Francisco, CA, 1999.
2.N. Abe and A. Nakamura. Learning to optimally schedule internet banner advertisements. In Proc. 16th International Conf. on Machine Learning, pages 12–21. Morgan Kaufmann, San Francisco, CA, 1999.
3.R. Agrawal. Sample mean based index policies with $O(\log n)$ regret for the multi-armed bandit problem. Advances in Applied Probability, 27:1054–1078, 1995.
4.N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, New York, 1992.
5.P. Auer. Using upper confidence bounds for online learning. In Proceedings of the 41th Annual Symposium on Foundations of Computer Science, pages 270–293. IEEE Computer Society, 2000.
6.P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 322–331. IEEE Computer Society Press, Los Alamitos, CA, 1995.
7.P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. NeuroCOLT2 Technical Report NC2-TR-1998-025, Royal Holloway, University of London, 1998. Accessible via http at www.neurocolt.org.
8.P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. Journal version, 2000.
9.P. Auer and M. K. Warmuth. Tracking the best disjunction. Machine Learning, 32:127–150, 1998. A preliminary version has appeared in Proceedings of the 36th Annual Symposium on Foundations of Computer Science.
10.K. Azuma. Weighted sums of certain dependent random variables. Tohoku Math. J., 3:357–367, 1967.
11.D. A. Berry and B. Fristedt. Bandit Problems. Chapman and Hall, 1985.
12.M. Herbster and M. K. Warmuth. Tracking the best expert. Machine Learning, 32:151–178, 1998.
13.W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13–30, 1963.
14.L. P. Kaelbling. Associative reinforcement learning: A generate and test algorithm. Machine Learning, 15:299–319, 1994a.
15.L. P. Kaelbling. Associative reinforcement learning: Functions in $k$ -DNF. Machine Learning, 15:279–298, 1994b.
16.T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4–22, 1985.
17.N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994.
18.H. Robbins. Some aspects of the sequential design of experiments. Bulletin American Mathematical Society, 55:527–535, 1952.
19.R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.

Citation

MLA

Auer, P. “Using Confidence Bounds for Exploitation-exploration Trade-offs”. Journal of Machine Learning Research, vol. 3, no. 3, 2003, pp. 397–422, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.2212.

APA

Auer, P. (2003). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3(3), 397–422. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.2212

Chicago

Auer, P. 2003. “Using Confidence Bounds for Exploitation-exploration Trade-offs”. Journal of Machine Learning Research 3 (3): 397–422. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.2212.

Harvard

Auer, P. (2003) “Using confidence bounds for exploitation-exploration trade-offs”, Journal of Machine Learning Research, 3(3), pp. 397–422. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.2212.

Vancouver

1. Auer P (2003) Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research 3:397–422

BibTeX

@article{auer2003using,
  title = {Using confidence bounds for exploitation-exploration trade-offs},
  author = {Auer, Peter},
  year = {2003},
  journal = {Journal of Machine Learning Research},
  volume = {3},
  number = {3},
  pages = {397-422},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.2212}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Using Confidence Bounds for Exploitation-Exploration Trade-offs

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — High-Probability Regret Bound for SupLinRel in Linear Contextual Bandits

Knowl 2 — SupLinRel Algorithm

Knowl 3 — LinRel Confidence Bound Algorithm

Knowl 4 — High-Probability Tracking Regret Bound for ShiftBand

Knowl 5 — ShiftBand Algorithm

Knowl 6 — Associative Reinforcement Learning with Linear Value Functions

Knowl 7 — Adversarial Bandit Problem with Shifting Targets

Knowl 8 — Cumulative Bounds on Reconstruction Norms and Residuals via Spectral Potential

References

Citation

BibTeX

Access the Paper