Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms

AI summary

Overview

Research area: stochastic multi-armed bandits with structured (graph-encoded) reward functions, specifically the theory of asymptotically optimal algorithms and regret lower bounds.

Technical level: Advanced. The paper is written for readers comfortable with information-theoretic regret bounds, semi-infinite linear programming, dynamic programming, and subgradient methods.

Scope in one sentence: The paper gives the first computationally tractable procedure for solving the Graves-Lai optimization problem for multimodal bandits on tree graphs, which is the missing ingredient needed to run existing asymptotically optimal algorithms in this setting.

What This Paper Is About

The paper studies a stochastic multi-armed bandit with K arms where the mean rewards are not arbitrary but follow a "multimodal" structure: arms are vertices of a known tree graph G, and each mode is an arm whose mean reward is strictly greater than that of all its graph neighbors. The optimal arm must be found by sampling, and the learner knows that the reward vector has at most m modes with respect to G (m is known to the learner, and m > 1 is assumed).

The goal is to design algorithms whose regret matches the Graves-Lai information-theoretic lower bound. The obstacle is that this bound is defined by a semi-infinite linear program whose constraint set is highly non-convex and disconnected, so the paper's aim is to solve that program efficiently enough to make the existing asymptotically optimal algorithms usable.

Key Contributions

1. The first known computationally tractable algorithm for solving the Graves-Lai optimization problem for multimodal bandits. It combines discretization, dynamic programming, and projected subgradient descent, applies to a wide variety of reward distributions, and works for any tree graph.

2. A hardness result showing that any approach that represents the constraint set as a union of convex sets needs a number of components that grows exponentially with the number of modes m, which explains why closed-form or simple convex-programming approaches fail.

3. A structural characterization of the "most confusing parameter" — the minimizer of the constraint of the Graves-Lai program — showing where its modes must be located, which is what makes the dynamic programming search possible.

4. A demonstration that local search strategies, which are asymptotically optimal in the unimodal case, are suboptimal for multimodal bandits, so solving the Graves-Lai problem is unavoidable for optimality.

Main Findings

• The lower bound is a semi-infinite linear program. For any uniformly good algorithm, the asymptotic regret satisfies lim inf_{T→∞} R(μ,T)/ln T ≥ C(m,μ) for all μ in F_{≤m}, where C(m,μ) is the value of P_GL: minimize ηᵀΔ subject to inf_{λ in B(m,μ)} ηᵀ d(μ,λ) ≥ 1 and η ≥ 0, with B(m,μ) = {λ in F_{≤m}, λ_{k*(μ)} = μ*, k*(λ) ≠ k*(μ)}.

• Solving P_GL yields asymptotic optimality. If a solution to the Graves-Lai problem can be computed, the OSSB algorithm with parameters ε = γ = 0 attains lim sup_{T→∞} R(μ,T)/ln T ≤ C(m,μ) for Gaussian rewards with variance one. This is a recall of Theorem 2 of prior work.

• The constraint set is intrinsically hard to decompose. If B(m,μ) is written as a union of U(K,m) convex sets, then for any m > 1, U(K,m) ≥ ((deg(G)−1)m)!/(deg(G)m)! · (K−(deg(G)+1)m)^m, which grows exponentially with m. For a line graph with K = 100 nodes and m = 5 modes, U(K,m) must be greater than 10^5.

• Most confusing parameters can take unexpected forms. In the unimodal case the most confusing parameter is obtained by perturbing a single neighbor of the optimal arm. For m > 1 this intuition fails: depending on η, it may be more confusing to set λ_k = μ* for an arm outside the neighborhood of the modes, and to force λ_{k'} = λ_ℓ for some k' that is a mode of μ other than the optimal arm and ℓ adjacent to it.

• Simple cases are solvable directly. If k lies in N(μ), the set of modes and neighbors of modes, or if |M(μ)| < m, then inf_{λ in B_k(m,μ)} ηᵀd(μ,λ) = η_k d_k(μ_k, μ*), attained at λ = μ + (μ* − μ_k)e^(k).

• The solution's modes are tightly constrained. The modes of the solution to the subproblem P_GL(k) satisfy M(λ*) ⊂ M(μ) ∪ {k}. When |M(μ)| = m, one has |M(μ) ∪ {k}| = m+1, so exactly one mode k' of μ is not a mode of λ*, and one can assume k' ≠ k*(μ).

• The search space is bounded. There is a solution η* with η* in [0, B(μ)]^K where B(μ) = (1/Δ_min) Σ_{k: Δ_k>0} Δ_k / d_k(μ_k, μ*); B(μ) can be interpreted as the regret predicted by the Lai-Robbins bound in absence of a multimodal structure, divided by the minimal gap.

• A controlled discretization exists. With the uniform grid D(n,μ) = {μ_* + (i/n)(μ* − μ_), i in [n]}, there is λ̃ in B_{k,k'}(m,μ) ∩ D(n,μ)^K such that ηᵀd(μ,λ̃) − ℭ(μ)/n ≤ min_{λ in B_{k,k'}} ηᵀd(μ,λ) ≤ ηᵀd(μ,λ̃), where ℭ(μ) = diam(G)(μ − μ_*)𝔄(μ)𝔅(μ)K. The approximation error vanishes inversely with n.

• Dynamic programming solves each discretized subproblem. Each P̃_GL(k,k') can be solved in time and memory O(nK) using the recursion of Proposition 8 (forward pass from leaves to root) plus a backward reconstruction pass. Solving all subproblems and finding the most confusing parameter takes O(K²mn) time; the subproblems are independent and parallelizable. A more involved dynamic program in the appendix runs in O(Kn) without parallelism.

• Reward distribution assumptions. Assumption 1 requires each relative entropy λ_k ↦ d_k(μ_k, λ_k) to be strictly decreasing below μ_k and strictly increasing above it. Assumption 2 requires a Lipschitz property with constant 𝔄(μ) over [μ_, μ]^K; for Gaussian rewards 𝒩(0,1) it holds with 𝔄(μ) = μ* − μ_*.

• Worked example. On a line graph with μ = (1,2,4,2,3), η = (0.01,0.25,1,0.25,1), Gaussian rewards with variance one, k*(μ) = 3, M(μ) = {3,5} and N(μ) = {2,3,4,5}. For k in N(μ), the constraint value equals 1/2; otherwise k must be 1 and the only removable mode is k' = 5.

• Numerical experiments. The provided paper content does not report regret simulations or benchmark tables; the code is released publicly at https://github.com/wilrev/MultimodalBandits.

Methodology in Plain English

The Graves-Lai bound tells you the minimum rate at which each suboptimal arm must be sampled, but computing it requires minimizing a convex function over a wildly non-convex feasible set of "confusing" reward vectors that would fool the learner. The paper's approach is to shrink that set without losing optimality.

First, the authors prove the feasible set can be broken into separate pieces indexed by which arm becomes the winner in the confusing parameter. Most of these pieces are trivial: whenever the alternative winner is a neighbor of a mode, or the true problem has fewer than m modes, the answer has a simple closed form. Only the remaining cases matter.

Second, they prove a structural fact about those remaining cases: the confusing parameter's modes can only be the true modes of μ plus the alternative winner, minus exactly one true mode. That reduces an unbounded search over reward vectors to a search over which mode gets removed and what value it takes.

Third, they replace the continuous range of values with a finite grid and prove the resulting error shrinks like one over the number of grid points, without disturbing the mode structure. On a tree rooted at the alternative winner, the constrained minimization then becomes a dynamic programming recursion: each node stores the cheapest cost achievable in its subtree as a function of its own value and of whether it is above or below its parent. A forward pass from leaves to root fills these tables in O(nK) time, and a backward pass reconstructs the best vector.

Finally, these inner solvers are wrapped in a projected subgradient descent loop, which iteratively updates the sampling rates η and recomputes the most confusing parameter until the Graves-Lai solution is found.

Why This Matters

Impact on research: structured bandits have had asymptotically optimal algorithms for years, but for many structures those algorithms are unusable in practice because they must repeatedly solve the Graves-Lai program. This paper shows that for multimodal rewards on trees, that program is solvable in polynomial time, and simultaneously proves that cheaper local search alternatives cannot be optimal. It also gives a negative result quantifying exactly why the naive convex-decomposition route explodes.

Real-world applications (as identified by the paper):

• Pricing, which the paper cites as an interesting application area for bandit problems with multimodal rewards.
• Objective functions that are neither convex nor unimodal, such as the empirical risk of deep neural networks.
• Bayesian optimization style methods for optimizing or sampling multimodal functions.
• MCMC-style sampling of multimodal distributions, and multimodal functions studied in active learning.

Industry relevance: any system whose reward landscape has several competing optima — price points, configuration tuning, or content selection — is exactly a multimodal bandit. Being able to compute the optimal exploration schedule means such systems can stop hunting locally and allocate experimentation across the right arms, and the released code makes trial-scale deployment feasible.

Future Directions

• Extending the solver beyond trees, since the dynamic programming recursion depends crucially on the graph being a tree and on a depth-first rooting at the alternative winner.
• Reducing the O(K²mn) cost of finding the most confusing parameter at each subgradient step, or exploiting the O(Kn) unparallelized dynamic program described in the appendix, to make the solver usable for large K.
• Characterizing the finite-time regret and empirical behavior of the resulting algorithms, since the provided content presents the asymptotic guarantees but no simulation results.
• Relaxing or broadening Assumptions 1 and 2 on the relative entropy, which currently restrict the family of reward distributions for which the approach is proved correct.

Target Audience

Researchers and graduate students in machine learning and decision theory working on bandits, sequential decision making, and structured exploration; theoreticians interested in the Graves-Lai framework, semi-infinite programming, and dynamic programming over graphs; and practitioners who need principled exploration schedules for reward landscapes with multiple optima and who can read the accompanying code.

Authors’ abstract

We consider a stochastic multi-armed bandit problem with i.i.d. rewards where the expected reward function is multimodal with at most m modes. We propose the first known computationally tractable algorithm for computing the solution to the Graves-Lai optimization problem, which in turn enables the implementation of asymptotically optimal algorithms for this bandit problem. The code for the proposed algorithms is publicly available at https://github.com/wilrev/MultimodalBandits