Source-linked AI summary
Thompson Sampling for Complex Bandit Problems
Aditya Gopalan, Shie Mannor, Yishay Mansour
TL;DR
Complex bandit problems involve dependent complex actions and feedback that may expose only aggregate rewards, making standard independent-arm analyses insufficient. The paper develops a posterior-based Thompson sampling analysis for general parameter, action, observation, and likelihood spaces. It obtains logarithmic regret with constants that capture coupling across actions, while noting that the additive constant in the bound may be a proof artifact.
Problem
Complex bandits can involve dependent rewards and aggregate observations, while existing analyses rely on specialized conjugate or closed-form posterior structures.
Method
The paper analyzes Thompson sampling through posterior evolution and a path-based optimization over action and feedback structures.
Results
The resulting regret bound scales logarithmically with time and has improved constants that capture correlations across complex actions.
Takeaways & Limitations
The framework applies broadly without conjugacy or closed-form posteriors and can be implemented with particle filters for complex bandit scenarios.
Takeaways & Limitations
The bound includes an additive constant B that may be large and depend on the total number of complex actions, although the authors believe it is a proof artifact.
Abstract
from arXiv · showhide
We consider stochastic multi-armed bandit problems with complex actions over a set of basic arms, where the decision maker plays a complex action rather than a basic arm in each round. The reward of the complex action is some function of the basic arms' rewards, and the feedback observed may not necessarily be the reward per-arm. For instance, when the complex actions are subsets of the arms, we may only observe the maximum reward over the chosen subset. Thus, feedback across complex actions may be coupled due to the nature of the reward function. We prove a frequentist regret bound for Thompson sampling in a very general setting involving parameter, action and observation spaces and a likelihood function over them. The bound holds for discretely-supported priors over the parameter space and without additional structural properties such as closed-form posteriors, conjugate prior structure or independence across arms. The regret bound scales logarithmically with time but, more importantly, with an improved constant that non-trivially captures the coupling across complex actions due to the structure of the rewards. As applications, we derive improved regret bounds for classes of complex bandit problems involving selecting subsets of arms, including the first nontrivial regret bounds for nonlinear MAX reward feedback from subsets.
1 Introduction
Complex bandits extend the basic MAB setting to dependent actions, aggregate feedback, and rewards that need not decompose across arms. The paper develops Thompson sampling and a general regret analysis for these settings, including posterior-based handling of complex information models.
- Motivation: Complex actions can have dependent rewards, as in ad selection, job scheduling, and routing problems.These settings may involve nonlinear aggregation or interdependent paths rather than independent action rewards.
- Motivation: Complex bandits may provide only aggregate feedback instead of individual rewards for each selected basic arm.For example, scheduling may reveal only the final makespan.
- Approach: Thompson sampling updates a posterior over basic-arm parameters, samples a parameter, and plays the complex action optimal for that sample.Posterior updates implicitly capture correlations among complex actions through shared basic parameters.
- Contributions: A posterior-based proof technique yields a general logarithmic regret bound whose constant captures coupling across complex actions.The bound applies with discrete priors placing nonzero mass on the true model and can improve over decoupled action-wise bounds.
- Gap: Existing general regret analyses rely on conjugate prior-posterior structures that break down for complicated, non-closed-form posteriors.The paper targets settings lacking those specialized assumptions.
- Empirical evaluation: Numerical studies evaluate particle-filter Thompson sampling in subset selection and job scheduling scenarios.The implementation uses sequential Monte Carlo to maintain and sample posterior distributions.
2 Setup and Notation
The model specifies i.i.d. latent random variables governed by an unknown parameter, complex actions, observations generated through a likelihood-linked function, and regret relative to the optimal action. Thompson sampling operates by maintaining a prior over parameters for posterior updating.
- Model: The stochastic model uses i.i.d. random variables X_t in a space X, parametrized by an unknown true parameter θ* in Θ.The basic-arm example takes X as an N-dimensional reward space.
- Model: At each round, the learner chooses an action A_t from A and observes Y_t=f(X_t,A_t) in Y.The observation need not expose each basic arm’s reward separately.
- Objective: The optimal action a*(θ) maximizes expected reward under parameter θ, and regret compares realized rewards with those of a*(θ*).Regret can alternatively be represented through the number of suboptimal action plays under bounded rewards.
- Algorithm: Algorithm 1 initializes a prior π over Θ and updates it as actions and observations accumulate.The algorithm’s inputs are Θ, A, Y, and the likelihood l(y; a, θ).
- Abstract formulation: The general formulation can omit underlying basic arms and instead use parameter, action, observation, likelihood, and reward-function spaces.In that abstract model, the likelihood is l(y; a, θ).
3 Regret Performance: Overview
The overview analyzes posterior evolution by tracking how actions accumulate information against competing models. This produces a path-based regret characterization in KL-divergence geometry and establishes logarithmic scaling with improved constants for coupled complex bandits.
- Posterior evolution: Each action contributes a model-dependent loss determined by its marginal KL divergence from the true model.The marginal divergence compares the output distributions generated by playing that action under two parameters.
- Posterior evolution: The true model retains a constant posterior share, so Thompson sampling plays the true model’s optimal action with constant probability and accumulates Ω(t) optimal plays.This follows because the exponential loss factor is at most one for the true model.
- Elimination dynamics: Models supporting suboptimal actions are eliminated when their accumulated KL-weighted losses reach approximately log T.Different actions can contribute to eliminating the same bad model when their observations are informative about shared parameters.
- Path-based analysis: The path-based bound constrains play counts so that an eliminated action is not played after its elimination time.The resulting optimization tracks the sequence of action eliminations through the play-count lattice.
- Regret bound: The bound depends on the KL-divergence geometry and can be smaller than bounds treating all complex actions independently.For standard MABs, the general bound recovers essentially optimal known regret scaling.
- Formal result: Under mild assumptions, the rigorous high-probability large-horizon regret bound has logarithmic time scaling.The assumptions concern the parameter, action, observation, and prior spaces.
4 Regret Performance: Formal Results
The paper establishes a high-probability logarithmic regret bound for Thompson sampling in general stochastic complex bandits, under finite-space and finite-prior assumptions. The bound captures information coupling across actions and yields improved guarantees for subset selection with full or MAX feedback.
- 4 Regret Performance: Formal Results: The formal guarantees are limited by a finite prior and a potentially large additive constant B; continuous-prior guarantees are deferred because suitable adaptive neighborhoods remain unclear.The authors regard the finite-prior restriction as mainly technical, while identifying continuous-prior analysis as future work.
- 4 Regret Performance: Formal Results: The proof tracks general Bayes posteriors through a path-space concentration problem, accounting for coupled information across complex actions.The analysis uses a self-normalized concentration inequality to follow posterior evolution.
- 4 Regret Performance: Formal Results: Theorem 1 gives a high-probability large-horizon regret bound for Thompson sampling under assumptions on finite action and observation spaces, a finite prior containing the true model, and a unique best action.The theorem applies for sufficiently large T and probability at least 1 − δ.
- 4.1 Playing Subsets of Bandit Arms and Observing “Full Information”: For size-M subset actions with full feedback, the regret scales as O((N − M) log T) despite up to exponentially many actions in M.When M = 1, the scaling matches the optimal standard Bernoulli-bandit scaling obtained by specialized algorithms.
- 4.2 A General Regret Improvement Result & Application to MAX Subset Regret: With MAX feedback, only the maximum reward over the selected subset is observed, making zero feedback weakly informative and one feedback highly informative about constituent arms.This nonlinear aggregate-feedback setting is analyzed using the same general Thompson-sampling machinery.
- 4.2 A General Regret Improvement Result & Application to MAX Subset Regret: Proposition 2 guarantees an additive regret reduction when suboptimal models are distinguishable from the truth through sufficiently many actions using marginal KL-divergences.The result formalizes improvement over naive decoupled regret through a parameter-space measure of action coupling.
- 4.2 A General Regret Improvement Result & Application to MAX Subset Regret: The MAX-feedback corollary provides a non-trivial regret bound for the nonlinear maximum reward over selected arms under a discretized parameter space.The setting uses parameters drawn from a finite grid determined by β and R, with MAX as the feedback function.
5 Discussion & Future Work
The paper presents a general Thompson-sampling regret framework for complex bandits and identifies future applications to broader Bayesian-inspired learning settings.
- The paper develops a generic regret bound whose improved constants capture complex problem structure.The analysis views posterior evolution as a path-based optimization problem.
- Particle filters provide a practical way to implement Thompson sampling for complex posterior distributions.
- The posterior-concentration technique may support adversarial regret analyses for Bayesian-inspired algorithms.
- The paper suggests learning continuous bid-reward functions by estimating the bid curve in repeated online auctions.
- Large-scale reinforcement learning with complex, state-dependent Markovian dynamics remains unexplored in this framework.The paper also identifies continuous-state X-armed bandits and rigorous value-of-information characterizations as future directions.
A Proof of Theorem 1
The proof rewrites posterior evolution using action-specific reward samples and empirical observation distributions, then controls likelihood weights through KL divergence and concentration bounds.
- Bayes’ rule expresses posterior weights through each parameter’s likelihood of the observed history.
- For each action, the empirical observation distribution summarizes outcomes collected when that action was played.
- The marginal distribution θ_a contains the likelihoods of action a’s observations under parameter θ, while KL divergence measures distributional discrepancy.
- An equivalent probability space pre-generates independent action-specific observations and reveals the next unused sample when an action is played.
- The proof uses a self-normalized uniform deviation bound to control empirical distributions for every action.
- Under the good event, likelihood expressions have finite lower bounds uniformly over the finite parameter and action spaces.
A.1 Regret due to sampling from S′′
This proof component bounds regret from sampling parameters that remain distinguishable from the true model through suboptimal actions, using posterior concentration and KL separation.
- The analysis bounds posterior sampling probabilities using conditional filtration and the true parameter’s posterior mass.
- Every alternative parameter in S′′ is separated from the true parameter through at least one suboptimal action.
- Positive KL separation follows from the discrete prior assumption, enabling logarithmic control of samples from S′′.
- Uniform bounds and a union bound over suboptimal actions control the total contribution across actions.
A.2 Regret due to sampling from S′
This proof component eliminates suboptimal actions sequentially and shows that sampling from parameter sets associated with eliminated actions contributes only controlled regret.
- The proof constructs stopping times and nested eliminated-action sets over the horizon.
- After an action is eliminated, its effective play count is frozen at the elimination time, with a factor 1+ε modifying the threshold.
- Each suboptimal action has a unique elimination time under the fixed tie-breaking rule.
- Once eliminated, an action’s associated parameter set is sampled only a constant number of additional times.
- The resulting high-probability regret bound has the form B + C(log T), with B independent of T.
B Proof of Corollary 1
The proof identifies the optimal subset and partitions suboptimal subsets by their weakest basic arm. It then uses KL-divergence inequalities to bound the contribution of each such group and complete the regret bound.
- The optimal action is the subset a∗ = {N − M + 1, . . . , N}.
- Suboptimal subsets are partitioned according to the least-index basic arm they contain.Every suboptimal set contains an arm indexed at most N − M.
- Matching the optimal action's coordinates forces θj = µj for all j ≥ N − M + 1.The argument uses additivity of KL divergence for tuples of M independent rewards.
- For a suboptimal group indexed by i, θi ≥ µN−M+1 implies D(µi||θi) ≥ D(µi||µN−M+1).
- Summing the resulting bounds over all i from 1 through N − M yields the desired contradiction and completes the proof.
C Proof of Proposition 2 & Corollary 2
The section bounds the optimization controlling Thompson-sampling behavior and applies the result to subset actions with nonlinear MAX feedback. The application exploits the product-form Bernoulli feedback divergence and a combinatorial coverage property of subsets.
- Proposition 2: Proposition 2 upper-bounds the optimization problem under conditions involving a minimum divergence parameter and at least L sufficiently separated coordinates.
- Proposition 2: The proof reduces the optimization by relaxing divergence and gap quantities, then constructs a solution preserving the original objective value.
- Playing Subsets with Max reward: For MAX reward feedback, the marginal KL divergence of a subset is the Bernoulli KL divergence for the product of its arm parameters.
- Playing Subsets with Max reward: Pinsker’s inequality supplies a lower bound on the relevant divergences for discretized Bernoulli parameters.
- Playing Subsets with Max reward: Any two distinct parameter vectors in the discrete parameter space differ on at least L subset actions, using a combinatorial result about weight-M vertices of the hypercube.
- Playing Subsets with Max reward: For sufficiently large T, Proposition 2 bounds the total number of arm plays with probability at least 1 − δ, with logarithmic dependence on T.