Source-linked AI summary
Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
Wesley Cowan, Junya Honda, Michael N. Katehakis
TL;DR
The paper asks how quickly regret can grow for normal bandits when both means and variances are unknown, and addresses a proof gap around a proposed optimal policy. It modifies the index policy and establishes asymptotic optimality with finite-horizon regret bounds. The paper also discusses its policy alongside asymptotically optimal Thompson sampling.
Problem
For normal bandits with unknown means and variances, the open question is whether the proposed policy can be shown asymptotically optimal, within the class of uniformly fast convergent policies.
Source: §1 · pp. 1, 3, 4Method
The paper modifies the Burnetas and Katehakis index policy by using 2/(T_i(n)-2) in place of 2/T_i(n) under the radical.
Source: §1 · p. 4Results
Takeaways & Limitations
A slight index modification yields a policy whose asymptotic optimality the paper can prove, despite refuting the condition used in the earlier proof attempt.
Source: §1 · p. 4The authors do not claim the finite-horizon or remainder bounds are the best achievable for this policy; tighter bounds may be possible.
Source: §2 · p. 7
Abstract
from arXiv · showhide
Consider the problem of sampling sequentially from a finite number of $N \geq 2$ populations, specified by random variables $X^i_k$, $ i = 1,\ldots , N,$ and $k = 1, 2, \ldots$; where $X^i_k$ denotes the outcome from population $i$ the $k^{th}$ time it is sampled. It is assumed that for each fixed $i$, $\{ X^i_k \}_{k \geq 1}$ is a sequence of i.i.d. normal random variables, with unknown mean $\mu_i$ and unknown variance $\sigma_i^2$. The objective is to have a policy $\pi$ for deciding from which of the $N$ populations to sample form at any time $n=1,2,\ldots$ so as to maximize the expected sum of outcomes of $n$ samples or equivalently to minimize the regret due to lack on information of the parameters $\mu_i$ and $\sigma_i^2$. In this paper, we present a simple inflated sample mean (ISM) index policy that is asymptotically optimal in the sense of Theorem 4 below. This resolves a standing open problem from Burnetas and Katehakis (1996). Additionally, finite horizon regret bounds are given.
1. Introduction and Summary
The paper studies sequential sampling from normal populations with unknown means and variances, aiming to maximize expected reward by minimizing regret. It introduces a modified index policy and establishes its asymptotic optimality while giving finite-horizon regret bounds.
1. Introduction and Summary
- The setting is a finite collection of normal bandits with unknown means and variances, where the controller seeks the highest expected cumulative reward.Regret measures the expected loss from not knowing the parameters and choosing a maximum-mean bandit at every round.Source: §1 · pp. 1–2
- Auer et al. (2002)'s πACF policy is uniformly fast convergent because its regret is bounded by MACF(μ,σ²) log n plus a lower-order term.The paper presents this result as prior work establishing that uniformly fast convergent policies exist.Source: §1 · pp. 2–3
- Uniformly fast convergence requires logarithmic sampling of suboptimal populations, while the logarithmic ACF regret upper bound can remain above the distribution-specific lower bound.Asymptotic optimality is defined by matching the lower-bound coefficient of log n.Source: §1 · p. 3
- The paper refutes the conjecture blocking Burnetas and Katehakis (1996b)'s proof, without showing their policy fails, and proves a slight modification asymptotically optimal.The modification changes the index's exponent from 2/T_i(n) to 2/(T_i(n)-2).Source: §1 · p. 4
- The paper also gives finite-horizon regret bounds, derives an asymptotic remainder bound, and compares its policy with asymptotically optimal Thompson sampling.The comparison concerns finite horizons and the two policies' practical differences.Source: §1 · p. 5
2. The Optimality Theorem and Finite Time Bounds
The section gives finite-horizon regret bounds for πCHK, uses them to establish its asymptotic optimality, and bounds the sub-logarithmic remainder. It also describes simulations and a comparison of theoretical bounds and regret convergence.
The Optimality Theorem and Finite Time Bounds
- For n ≥ 3N and ε ∈ (0,1), Theorem 3 provides a finite-horizon regret bound for πCHK.The stated bound can be improved to remove its lnln(n) dependence, at the cost of a larger power of 1/ε.Source: §2 · pp. 5–6
- πCHK is asymptotically optimal: its regret divided by ln(n) converges to MBK(µ,σ2).Theorem 4 establishes this result; Figure 2 also depicts the convergence.Source: §2 · p. 6, Figure 2 · p. 11
- Theorem 5 bounds regret by MBK(µ,σ2)ln(n) + O((ln(n))^3/4 lnln(n)), making the remainder sub-logarithmic.The paper says the bounds are sufficient to demonstrate asymptotic optimality but does not claim they are the best achievable for πCHK.Source: §2 · pp. 6–7
- The proof bounds expected sampling of each suboptimal bandit and then uses those bounds to bound regret.It adapts techniques for the known-variance case to unknown variance and uses Proposition 2’s probability bound.Source: §2 · pp. 5, 7
- The simulation compares πCHK, πACF, and a greedy policy over 100,000 activations, with 10,000 replications on six populations.Figure 1 shows regret over the first 10,000 activations and over the full horizon; the passage does not state which policy performs best.Source: §2 · p. 10, Figure 1 · p. 11
- Figure 2 compares theoretical regret bounds BπACF(n) and BπCHK(n), with πCHK using ε = (ln n)^(1/4), and shows RπCHK(n)/ln(n) converging to theoretical lower bound MBK(µ,σ2).Source: Figure 2 · p. 11, §2 · p. 11
3. A Comparison of πCHKand Thompson Sampling
The paper compares asymptotically optimal policies πCHK and πTS over finite horizons, finding generally comparable expected regret and context-dependent differences in which policy performs better.
3. A Comparison of πCHKand Thompson Sampling
- Honda and Takemura (2013) proved that their Thompson sampling algorithm is asymptotically optimal for α < 0.The stated limit is RπCHK(n)/ln n = MBK(µ,σ2).Source: §3 · p. 11
- πTS is randomized, whereas πCHK's decisions are determined by the bandit results observed so far.The comparison uses a uniform prior α = −1 and replicated simulations to estimate expected regret.Source: §3 · p. 12
- General sampling suggests πTS and πCHK generally produce comparable expected regret; πTS is slightly superior with roughly equal variances across bandits, while πCHK has an edge when optimal bandits have relatively large variance.Source: §3 · p. 12
- In the pictured cases, the policy with lower expected regret also has lower sample-regret variance; additional experiments suggest it may have a slightly heavier tail toward larger regret.Figure 4 compares sample-regret variance for the two policies across the same two parameter sets.Source: §3 · p. 12, Figure 4 · p. 13
Appendix A. Additional Proofs
Appendix A supplies auxiliary proof steps and inequalities, including a counterexample to Conjecture 1 and bounds used in the paper's analysis.
Appendix A. Additional Proofs
- The proof converts an integral into a probability by interpreting its integrand as the joint density of U and Z.It also invokes a normal-tail bound and bounds involving e^−x and a ratio of Gamma functions.Source: Appendix A · p. 16
- Remark 4 notes that alternative bounds could replace the chosen exponential inequality and affect how the resulting probability bound is used, including in Theorem 3.The text also suggests considering the bound e^−x ≤ 1/x similarly.Source: Appendix A · p. 16
- Proposition 6 states that Conjecture 1 is false for each i when ε > 0.Source: Appendix A · p. 16