PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Thompson Sampling

Weitong Zhang, Dongruo Zhou, Lihong Li, Quanquan Gu

arXiv:2010.00827v2cs.LGstat.ML

TL;DR

Contextual bandits require effective exploration and exploitation, and the paper adapts Thompson Sampling to deep neural networks through a reward posterior. NeuralTS combines neural-network reward estimates with posterior-based sampling, achieves a near-optimal regret bound, and performs competitively across benchmark datasets. The authors identify unresolved limits concerning optimization steps, finite-arm regret rates, and neural-network behavior beyond the neural tangent-kernel regime.

  • Problem

    Contextual bandits require balancing exploration and exploitation, while existing Thompson Sampling approaches with neural networks motivate a method with stronger neural-network-specific theoretical guarantees.

  • Method

    NeuralTS maintains a Gaussian posterior for each arm’s reward, uses a neural network for the posterior mean, and bases uncertainty on neural-network features while updating parameters through regularized gradient descent.

  • Results

    NeuralTS achieves an e O(edT^1/2) regret bound and performs competitively against multiple strong baselines, with performance among the best on 6 datasets and significantly better than all other baselines on 2.

  • Takeaways & Limitations

    The analysis and experiments support NeuralTS as a theoretically grounded neural-network approach to contextual-bandit exploration.

  • Takeaways & Limitations

    The analysis requires multiple gradient-descent steps per round, and matching the e O(dT^1/2) finite-arm rate remains an open problem; neural-network behavior beyond the neural tangent-kernel regime also remains to be studied.

Abstract

from arXiv · show

Thompson Sampling (TS) is one of the most effective algorithms for solving contextual multi-armed bandit problems. In this paper, we propose a new algorithm, called Neural Thompson Sampling, which adapts deep neural networks for both exploration and exploitation. At the core of our algorithm is a novel posterior distribution of the reward, where its mean is the neural network approximator, and its variance is built upon the neural tangent features of the corresponding neural network. We prove that, provided the underlying reward function is bounded, the proposed algorithm is guaranteed to achieve a cumulative regret of $\mathcal{O}(T^{1/2})$, which matches the regret of other contextual bandit algorithms in terms of total round number $T$. Experimental comparisons with other benchmark bandit algorithms on various data sets corroborate our theory.

1 INTRODUCTION

The paper introduces NeuralTS to combine Thompson Sampling with neural networks for contextual bandits, addressing exploration–exploitation while targeting strong regret guarantees and empirical performance.

  • Problem setting: Contextual bandits require choosing among arms using observed arm-specific feature vectors while balancing exploration and exploitation over T rounds.The setting is motivated by applications including recommendation, advertising, robotic control, and healthcare.
  • Contribution: NeuralTS incorporates Thompson Sampling exploration with neural networks and provides, to the authors’ knowledge, the first near-optimal regret bound for neural-network-based Thompson Sampling.It samples estimated rewards from a posterior rather than sampling network parameters.
  • Contribution: The algorithm differs from NeuralLinear by modeling weight uncertainty across all network layers rather than only the last layer.Other neural Thompson Sampling implementations sample parameters, whereas NeuralTS samples the estimated reward from its posterior.
  • Theory: e O(edT^1/2) regret is obtained, where ed is the effective dimension and T is the number of rounds.The bound is comparable to previous results when specialized to linear settings where effective dimension equals feature dimension.

2 PROBLEM SETTING AND PROPOSED ALGORITHM

The paper formulates contextual K-armed bandits and introduces Neural Thompson Sampling, which samples scalar rewards from neural-network-based posteriors. Its posterior mean comes from a neural network, while its analysis accounts for all network layers and gradient-based optimization.

  • Problem Setting: At each round, the agent observes K contextual vectors, selects one arm, receives its reward, and seeks to minimize pseudo-regret over T rounds.The optimal arm is defined as the one with the highest expected reward.
  • Problem Setting: NeuralTS estimates rewards with a fully connected depth-L neural network and uses its parameter gradient as the neural tangent feature.The network has width m, depth L ≥ 2, and parameter vector θ containing all layer weights.
  • Neural Thompson Sampling: NeuralTS maintains a Gaussian posterior for each arm’s scalar reward, samples one reward per arm, and selects the arm with the largest sample.The posterior mean is the neural-network output, while the sampled variance uses the gradient features and exploration variance ν.
  • Neural Thompson Sampling: The posterior mean is obtained by solving an ℓ2-regularized square-loss minimization problem centered at the randomly initialized network parameters.Gradient descent with step size η and J iterations is used to solve the non-convex optimization problem.
  • Algorithmic Differences: Unlike typical neural-network Thompson Sampling, NeuralTS samples scalar rewards rather than network parameters, simplifying implementation when neural networks have many parameters.Unlike linear or kernelized Thompson Sampling, it does not use a closed-form posterior and instead relies on gradient descent.
  • Algorithmic Differences: NeuralTS maintains posterior distributions for parameters across all network layers rather than only the last layer, supporting its connection to deep-learning theory for regret analysis.This all-layer construction is identified as crucial to the paper’s theoretical guarantees.

3 REGRET ANALYSIS

The analysis connects NeuralTS to neural tangent kernel theory and establishes a high-probability regret bound under regularity and reward assumptions. The resulting order matches state-of-the-art contextual bandit bounds, while the required network width remains a theory–practice gap.

  • Assumptions: The analysis assumes an unknown reward function, sub-Gaussian noise, positive-definite NTK matrix, and normalized contexts with a symmetry condition.The NTK assumption also ensures the initial neural-network output is zero under the specified initialization.
  • NTK background: The NTK matrix connects deep neural networks with kernel methods and supports the effective-dimension complexity measure used in the regret analysis.Effective dimension describes the actual underlying dimension of the observed contexts and is related in order to maximum information gain.
  • Main theorem: Under Assumption 3.4 and specified parameter choices, Theorem 3.5 gives a high-probability regret bound for NeuralTS.The theorem also imposes requirements on network width, learning parameters, and confidence level.
  • Regret guarantee: The theorem implies NeuralTS regret is on the order of eO(edT 1/2), matching state-of-the-art bounds for several contextual bandit algorithms.The comparison is made with results for kernelized, linear, and neural contextual bandit methods.
  • Theory–practice gap: The required network width is a high-degree polynomial in T, L, and K, although experiments obtain good performance with m = 100.The paper attributes this discrepancy to limitations of current NTK theory and notes a doubling trick when T is unknown.

4 PROOF OF THE MAIN THEOREM

The proof combines posterior concentration, neural-network approximation control, and standard Thompson Sampling arguments. It bounds regret by controlling sampled rewards, mean-estimation error, saturated-arm selection, and accumulated posterior uncertainty.

  • Proof strategy: The proof must track neural-network approximation error in addition to the ingredients used by prior Thompson Sampling analyses.This error appears explicitly in the event controlling the difference between estimated and true rewards.
  • Concentration events: The events Eσ_t and Eμ_t control sampled-reward deviations and neural-network mean-estimation deviations, respectively.The latter includes the approximation term ϵ(m), while the former bounds sampled rewards using posterior variance.
  • Arm decomposition: Unsaturated-arm immediate regret is bounded using posterior standard deviation plus approximation error, while saturated arms are shown unlikely to be selected.The saturated-arm definition incorporates ϵ(m), unlike earlier Thompson Sampling analyses.
  • Cumulative control: The proof combines conditional per-round regret bounds with supermartingale and Azuma–Hoeffding arguments to control cumulative regret.Additional lemmas bound the accumulated minimum posterior standard deviations and related random fluctuations.

5 EXPERIMENTS

Experiments evaluate NeuralTS on UCI and MNIST classification benchmarks transformed into contextual bandits, comparing it with linear, kernelized, bootstrap, and neural baselines. NeuralTS performs competitively across datasets, with robustness to delayed rewards examined separately.

  • Experiment setup: The evaluation uses adult, covertype, magic telescope, mushroom, shuttle, and MNIST datasets, comparing NeuralTS with several linear, kernelized, bootstrap, and neural baselines.The experiments use standard contextual-bandit benchmark families and repeated runs.
  • Bandit construction: Classification instances are converted to disjoint contextual bandits, with reward 1 for a correct class and 0 otherwise.Cumulative regret is measured as the total number of classification mistakes.
  • Implementation: Experiments use a horizon of 10 000 except for mushroom, stop training at t = 1000, and approximate inverse matrices diagonally for speed.The remaining performance is evaluated after training stops, following prior experimental practice.
  • Experiment I: NeuralTS ranks among the best on 6 datasets and is significantly better than all other baselines on 2 datasets.The reported total regret measures cumulative classification errors and averages results over 8 runs with standard errors shown.
  • Experiment I: With the same function class, Thompson Sampling is competitive with and sometimes better than alternative exploration strategies, especially for neural networks.The paper also reports that linear representations tend to perform worse when rewards are nonlinear.
  • Experiment II: The delayed-reward experiment compares NeuralTS and Neural UCB while varying batch size, with results reported across UCI and MNIST datasets.Rewards arrive in batches rather than immediately, and total regret remains the evaluation measure.

6 RELATED WORK

Related work places NeuralTS within contextual-bandit exploration research spanning Thompson Sampling, UCB, and neural-network methods. The paper distinguishes its contribution by pairing neural models with a regret analysis that prior neural approaches lacked.

  • Thompson Sampling: Thompson Sampling is a long-standing exploration heuristic that has received substantial recent attention in contextual bandits.The paper cites its original proposal and directs detailed related-work discussion to the introduction.
  • Upper confidence bounds: UCB is a widely used alternative to Thompson Sampling with near-optimal regret results in linear, generalized-linear, and kernelized contextual bandits.These settings represent established theoretical applications of UCB-based exploration.
  • Neural methods: Neural contextual-bandit methods include deep feature mappings, last-layer exploration, and ensembles or boosted neural networks.The cited approaches show empirical promise, but the passage states that no regret guarantees were known for them.
  • Positioning: NeuralTS addresses this gap by combining neural-network exploration with a regret guarantee for the proposed method.Its contribution is positioned against neural approaches described as promising empirically but theoretically unsupported.

7 CONCLUSIONS

NeuralTS adapts Thompson Sampling to neural networks and achieves a theoretical regret bound while performing well empirically. The conclusions identify computational and theoretical directions that remain open.

  • Conclusions: NeuralTS adapts Thompson Sampling to neural networks and achieves an e O(edT^1/2) regret bound.The bound is derived using recent advances in deep learning theory.
  • Conclusions: NeuralTS works well empirically on benchmark problems compared with multiple strong baselines.
  • Future research: The current analysis requires multiple gradient descent steps to train the neural network in each round.The one-step case and its trade-off between optimization precision and regret minimization remain open.
  • Future research: Achieving the same e O(dT) regret rate as parametric linear and generalized linear bandits is an open problem for NeuralTS.
  • Future research: It remains to investigate whether neural networks can behave differently from their neural tangent kernels for neural contextual bandits.This question is motivated by results for some parameter regimes.
  • Experimental setting: Experiments use one-hidden-layer networks with 100 neurons, 100 gradient-descent iterations, and learning rate 0.001.The features are normalized to unit ℓ2-norm, and datasets are shuffled randomly.

A.2 DETAILED RESULTS

The detailed-results section reports total-regret evaluations across datasets, compares NeuralTS with baselines and Neural UCB under delays, and introduces the associated figure and table summaries.

  • Tables: Table 1 reports total regret at the last round across datasets, using means and standard deviations from 20 independent runs.
  • Tables: Table 2 counts significant wins, ties, and losses against seven other algorithms using a t-test at 90% significance.
  • Figures: Figure 3 compares NeuralTS with baseline methods on UCI and MNIST datasets using cumulative classification errors as total regret.Results are averaged over multiple runs with standard errors shown as shaded areas.
  • Figures: Figure 4 compares NeuralTS with Neural UCB on UCI and MNIST datasets under different delay scales.The results use total regret, averaged over multiple runs with standard errors shown as error bars.
  • Figures: Figure 5 compares the running time of NeuralTS, Neural UCB, and ε-greedy neural-network methods on UCI and MNIST datasets.

A.3 RUN TIME ANALYSIS

NeuralTS and NeuralUCB require more runtime than ε-greedy, while BootstrapNN is slower still because it trains several neural networks each round.

  • Runtime comparison: NeuralTS and NeuralUCB are about 2 to 3 times slower than ε-greedy for neural networks.The additional runtime is attributed to calculating neural-network gradients for each input context.
  • Runtime comparison: BootstrapNN is often more than 5 times slower than ε-greedy because it trains several neural networks at each round.

B PROOF OF LEMMAS IN SECTION 4

The appendix proves technical lemmas using conditions, Gaussian concentration, union bounds, and a time-dependent choice of confidence parameter.

  • Proof setup: Under Condition 4.1, the proof establishes a set of inequalities used in the analysis.
  • Proof setup: The proof treats the constants C_m,1 through C_m,4 as positive absolute constants.
  • Gaussian bounds: A Gaussian concentration bound controls the probability that a normally distributed variable lies within β standard deviations of its mean.
  • Gaussian bounds: The estimated reward is sampled from a Gaussian distribution centered at the neural-network prediction with a variance term.The concentration lemma is applied conditional on the history and arm.
  • Proof aggregation: A union bound extends the probability control across the K arms at each time step.
  • Proof aggregation: Choosing c_t = √(4 log t + 2 log K) yields the stated probability bound.

B.2 PROOF OF LEMMA 4.3

The proof of Lemma 4.3 combines approximation, concentration, and kernel-comparison bounds to control the neural and linearized models under sufficient network width. These bounds are assembled through union bounds to obtain the lemma’s stated result.

  • Proof strategy: The proof first invokes auxiliary lemmas controlling neural-network approximation, reward-noise concentration, and the relationship between linearized and neural tangent kernels.The argument uses Lemmas B.3–B.7 and combines their high-probability events.
  • Noise control: The proof bounds the quadratic contribution of reward noise through a log-determinant inequality for an R-sub-Gaussian process.The resulting bound contains log det((1 + η)I + K_t) and a confidence term involving log(1/δ).
  • Kernel comparison: The linearized-kernel complexity is related to the neural tangent kernel through determinant bounds and the closure property established in Lemma B.7.The proof uses log-det identities, λ = 1 + 1/T, and the kernel comparison to control the resulting expression.
  • Approximation control: The target reward function is compared with the linearized network using the approximation bound and the identity relating observed rewards to expected rewards plus noise.The proof explicitly uses the triangle inequality and r_t−1 = h_t−1 + ϵ_t−1.
  • Conclusion: The conclusion follows after combining the preceding bounds, controlling the difference between linearized and actual uncertainties, and rescaling δ after the union bound.The final probability adjustment replaces δ by δ/5.

C PROOF OF AUXILIARY LEMMAS IN APPENDIX B

The auxiliary proofs establish neural tangent kernel properties needed for the main analysis, including parameter stability, gradient and function linearization, kernel similarity, and effective-dimension control. They also show that the effective dimension is at most d′ + 1 when contexts concentrate near a d′-dimensional subspace.

  • NTK properties: The NTK lemmas control parameter movement, gradient norms, function linearization, gradient changes, and kernel behavior near the random initialization.These results are stated under conditions on the network width, learning rate, and parameter neighborhood.
  • Parameter stability: With high probability, the trained parameters remain within a prescribed distance of the initialization, enabling the subsequent local NTK bounds.Lemma C.1 provides the parameter-distance control used by later lemmas.
  • Linearization: The neural network’s function and gradient are controlled by their linearized counterparts when the parameters stay near initialization.The cited lemmas bound function-linearization error and gradient differences over the relevant contexts.
  • Kernel comparison: The linearized kernel and NTK kernel are shown to be close when the network width is sufficiently large.The proof uses determinant comparisons and a width condition involving T, K, L, and δ.
  • Effective dimension: ed ≤ d′ + 1 when the contexts’ NTK feature mappings lie near a d′-dimensional subspace and the remaining eigenvalues are at most 1/(TK).The argument characterizes the NTK feature mapping using spherical harmonics and bounds the effective dimension under this spectral condition.
Loading 2010.00827v2…