PaperlayerView exact revision on arXiv

Source-linked AI summary

An Asymptotically Optimal Policy for Finite Support Models in the Multiarmed Bandit Problem

Junya Honda, Akimichi Takemura

arXiv:0905.2776v3math.STstat.TH

TL;DR

The multiarmed bandit problem asks how to choose among arms with unknown reward distributions while balancing exploration and exploitation. This paper proposes MED, a policy proved asymptotically optimal for finite-support models. Its divergence criterion can be computed by convex optimization, and the authors identify finite support as a boundary of their theoretical analysis.

  • Problem

    Choosing arms with unknown reward distributions requires balancing learning which arm is best against the reward lost by pulling inferior arms.

    Source: §1 · p. 1

  • Method

    MED chooses arms using a minimum empirical divergence criterion based on empirical reward distributions and the current best sample mean.

    Source: §1 · p. 3, §3 · p. 5

  • Results

    MED achieves the asymptotic bound for finite-support models and its divergence computation is a univariate convex optimization problem.

    Source: §3.2 · p. 8, §5 · p. 25

  • Takeaways & Limitations

    The authors conclude that MED is efficiently implementable through convex optimization for finite-support models.

    Source: §5 · p. 25

    The theoretical analysis assumes finite support; optimality for continuous bounded support is conjectured, though simulations show MED works nicely there.

    Source: §3 · p. 5, §5 · p. 25

Abstract

from arXiv · show

We propose minimum empirical divergence (MED) policy for the multiarmed bandit problem. We prove asymptotic optimality of the proposed policy for the case of finite support models. In our setting, Burnetas and Katehakis has already proposed an asymptotically optimal policy. For choosing an arm our policy uses a criterion which is dual to the quantity used in Burnetas and Katehakis. Our criterion is easily computed by a convex optimization technique and has an advantage in practical implementation. We confirm by simulations that MED policy demonstrates good performance in finite time in comparison to other currently popular policies.

1 Introduction

The multiarmed bandit problem requires balancing exploration of uncertain reward distributions against exploitation of the best-known arm. MED is proposed as an asymptotically optimal policy for finite-support models, using an empirically computed divergence criterion intended to be practical to optimize.

1 Introduction

  • The bandit dilemma is that identifying an optimal arm requires repeated pulls, while repeatedly pulling an inferior arm loses reward.Source: §1 · p. 1
  • Burnetas and Katehakis extended the asymptotic framework to multiparameter and non-parametric models, while practical UCB policies have theoretical or computational drawbacks.UCB-tuned is widely used for its simulation performance, but its consistency is unknown; other analyzed UCB policies do not necessarily achieve the logarithmic-term bound.Source: §1 · p. 2
  • MED is proved asymptotically optimal for distributions with finite bounded support, a broader model than the specific finite-support model used in.The paper also reports simulation performance comparable to UCB policies.Source: §1 · p. 3
  • An inferior arm may wait roughly exp(n_i D_min(F_i, µ*) ) rounds after its n_i-th play, motivating MED to pull it with probability exp(−n_i D_min(F_i, µ*)).MED substitutes the arm’s empirical distribution and the current best sample mean into D_min.Source: §1 · p. 3
  • MED computes D_min from empirical rewards, a criterion dual to the Burnetas–Katehakis quantity and suited to univariate convex optimization.Its smooth dependence on the current best sample mean allows the previous round’s value to approximate the current one; the paper contrasts this with the harder nonlinear constraint for (2).Source: §1 · p. 3
  • MED is a probability-matching policy whose arm probabilities are determined by normalized maximum likelihood rather than posterior probability.Probability matching selects each arm according to how likely it is to be optimal.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the distribution and arm notation used in the analysis and state the asymptotic lower-bound framework. They also define the divergence-based distinguishability quantity used to express that bound.

2 Preliminaries

  • For a distribution F, F(A) denotes the probability of a reward in A and E(F) its expected value; the K-arm model is the product family F^K.Source: §2 · p. 4
  • The notation defines each arm’s expected value µ_j, the best expected value µ*, and the number of pulls T_j(n) through round n.The empirical distribution and mean use the first t rewards, while the current best empirical mean is the maximum across arms.Source: §2 · p. 4
  • D_inf measures how distinguishable a distribution is from distributions with expectation greater than µ; it is infinite if none exist.Source: §2 · p. 4
  • For an inferior arm under a consistent policy, the Burnetas–Katehakis bound uses D_inf to characterize the asymptotic lower bound on expected pulls.The bound applies when the arm’s expected value is below µ* and its D_inf is positive and finite.Source: §2 · pp. 4–5

3 Asymptotically Optimal Policy for Finite Support Models

This section presents the minimum empirical divergence (MED) policy for finite-support distributions with known bounded support and establishes its asymptotic optimality. It describes computation of the divergence criterion by univariate convex optimization and develops the probability bounds and optimization arguments used in the proof.

3 Asymptotically Optimal Policy for Finite Support Models

  • The finite-support model assumes distributions have finite support within known bounds, and the optimality proof applies to that model because finite support enables use of the method of types.Finiteness cannot be determined from finite samples, and policies for A also apply to distributions supported anywhere within the bounds.Source: §3 · p. 5

3.1 Optimality of the Minimum Empirical Divergence Policy

  • Under MED, the theorem establishes asymptotic optimality for finite-support models, with the suboptimal-arm bound expressed using Dmin(Fi, µ∗, A) and log N.The result holds when one arm has the highest mean and every other arm has a strictly lower mean.Source: §3.1 · p. 6
  • MED extends the bound achieved by the policy in to settings where the support set X is not assumed known.The corollary gives the bound in terms of Dmin(Fi, µ, AX).Source: §3.1 · p. 7

3.2 Computation of Dmin and Properties of the Minimizer

  • Dmin can be computed by maximizing a concave function h(ν), yielding a univariate convex optimization problem that can be solved with iterative methods such as Newton’s method.For any F in A, the minimization can be restricted to distributions supported on {0} ∪ supp(F).Source: §3.2 · pp. 7–8

3.3 Proofs of Theorem 3 and 5

  • The proof establishes that Dmin is increasing in µ, lower semicontinuous in F, and continuous for µ < 0; it also has a uniformly positive increase between µ′ and µ when E(F) < µ′ < µ.Continuity at µ = E(F) is nontrivial because differentiability is established only for µ > E(F).Source: §3.3 · pp. 9–10
  • Theorem 3’s proof bounds P_N using a counting argument and Sanov’s theorem.It notes that at most one n can satisfy the stated intersection condition, then combines the resulting bounds with Sanov’s theorem.Source: §3.3 · pp. 15–16
  • Strict concavity of h(ν) makes ν* unique in Theorem 5(i).The proof excludes the degenerate case using the assumption E(F) < μ.Source: §3.3 · p. 16
  • Kuhn–Tucker conditions derive (11)–(13) by treating E_F[μ/X] ≤ 1 and E_F[μ/X] ≥ 1 separately.For the first case, the proof obtains (12) and uses concavity for (11); for the second, it obtains (11) and (13).Source: §3.3 · pp. 17–18
  • Theorem 5(ii)’s proof uses convexity of w(x, ν) and differentiability of D′_min(F, μ) in its treatment of E_F[μ/X] ≥ 1.The proof also identifies a value of ν at which the right-hand side of (32) is zero when E_F[μ/X] = 1.Source: §3.3 · pp. 18–19

4 Experiments

The experiments compare MED with UCB-tuned and UCB2 across six distribution settings. MED generally performs best and tracks the asymptotic regret bound, with Distribution 1 an exception where it performs worst.

Implementation

  • The implemented Dmin computation uses Newton’s method with bounded updates and has complexity O(r |supp(F)|).For large or continuous supports, the implementation reuses past Dmin values when the estimated best-arm mean changes little.Source: §4 · pp. 19–20

Experimental setup

  • The six test settings span two-arm cases, difficult-to-distinguish arms, larger arm counts and supports, and beta distributions.Distributions 1–4 are two-arm problems; Distributions 5–6 use larger arm counts and support sizes.Source: §4 · pp. 20–21, Table 1 · p. 21

Parameter choice

  • MED’s performance is not sensitive to r and d; the implementation approaches ideal MED as d → 0 and r → ∞.The remaining experiments use r = 2 and d = 0.01; the authors attribute this to an accurate local linear approximation and a useful initial value for ν.Source: §4 · p. 22, Figure 1 · p. 22

Policy comparison

  • MED’s regret slope is close to the asymptotic bound even for continuous-support distributions, although its optimality proof covers finite-support models.The experiments include beta distributions, whose continuous support lies outside the proved model.Source: §4 · pp. 21–22, Figure 7 · p. 24
  • MED performs best in five of six distributions, but worst in Distribution 1, where its regret constant needs improvement relative to UCB2.The reported theoretical logarithmic regret terms for Distribution 1 are 4.983 log n for MED and 5.025 log n for UCB2.Source: §4 · p. 22, Figure 2 · p. 23, Figure 3 · p. 23

5 Concluding remarks

MED achieves the asymptotic bound for finite-support models and can be implemented using convex optimization. The authors identify continuous-support optimality and finite-horizon guarantees as open directions.

5 Concluding remarks

  • MED achieves the asymptotic bound for finite-support models.The authors conjecture that optimality also holds for continuous bounded-support models, where MED performed well in simulations.Source: §5 · p. 25
  • Convex optimization provides an efficient implementation of MED.Source: §5 · p. 25
  • For continuous bounded-support models, MED performed well in simulations, but its optimality remains conjectural.Source: §5 · p. 25
  • Finite-horizon use calls for a finite-time bound and a policy that adjusts exploration as the remaining rounds shrink.The authors say the current MED policy should be improved when the horizon is known.Source: §5 · p. 25
Loading 0905.2776v3…