PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Exploration in Generalized Linear Bandits

Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, Craig Boutilier

arXiv:1906.08947v3cs.LGstat.ML

TL;DR

Generalized linear bandits have largely relied on upper confidence bounds, while posterior approximations for more complex models can be costly and lack regret guarantees. This paper proposes GLM-TSL and GLM-FPL, proves regret bounds, and reports strong logistic-bandit performance and encouraging neural-network experiments.

  • Problem

    Posterior approximations in bandits can be computationally costly and lack regret guarantees, motivating randomized GLM methods with guarantees.

    Source: §1 · p. 1, §6 · p. 8

  • Method

    GLM-TSL samples from a Laplace-approximated posterior, while GLM-FPL fits a GLM to past rewards perturbed by Gaussian noise.

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

  • Results

    Both algorithms achieve n-round regret ˜O(d√n log K); GLM-TSL improves the prior finite-arm bound, and GLM-FPL gives the first such bound for Gaussian perturbations in nonlinear models under an added feature assumption.

    Source: §1 · p. 1

  • Takeaways & Limitations

    Both algorithms perform well empirically in logistic bandits, and GLM-FPL's perturbation approach also yields encouraging neural-network experiments.

    Source: §7 · p. 8

    The GLM-FPL regret bound assumes each feature vector has at most one nonzero entry.

    Source: §4.5 · p. 6

Abstract

from arXiv · show

We study two randomized algorithms for generalized linear bandits. The first, GLM-TSL, samples a generalized linear model (GLM) from the Laplace approximation to the posterior distribution. The second, GLM-FPL, fits a GLM to a randomly perturbed history of past rewards. We analyze both algorithms and derive $\tilde{O}(d \sqrt{n \log K})$ upper bounds on their $n$-round regret, where $d$ is the number of features and $K$ is the number of arms. The former improves on prior work while the latter is the first for Gaussian noise perturbations in non-linear models. We empirically evaluate both GLM-TSL and GLM-FPL in logistic bandits, and apply GLM-FPL to neural network bandits. Our work showcases the role of randomization, beyond posterior sampling, in exploration.

1 Introduction

Generalized linear bandits model expected arm rewards as a known function of features and unknown parameters. This paper introduces two randomized algorithms, proves regret bounds, and reports strong empirical performance in logistic and neural-network settings.

1 Introduction

  • A generalized linear bandit models expected arm rewards as a known function of the dot product between known features and an unknown parameter vector.Source: §1 · p. 1
  • GLM-TSL samples a GLM from a Laplace-approximated posterior, while GLM-FPL fits a GLM to randomly perturbed past rewards.Source: §1 · p. 1
  • Both algorithms achieve n-round regret ˜O(d√n log K), with GLM-TSL improving the prior finite-arm bound and matching it in the infinite-arm setting.GLM-FPL is the first Gaussian-noise perturbation method with a regret bound for nonlinear models, under an additional assumption on arm features.Source: §1 · p. 1
  • Both algorithms perform at state-of-the-art levels in logistic bandits, and GLM-FPL is also applied to neural-network reward models.The paper reports that the neural-network experiments show GLM-FPL can learn complex mappings from features to rewards.Source: §1 · p. 1

2 Setting

The setting is a stochastic bandit with feature-vector arms and rewards generated by an underlying generalized linear model. The learner seeks to maximize expected cumulative reward over n rounds, equivalently minimizing regret.

2 Setting

  • A GLM models observations with an exponential-family distribution whose mean is µ(x^T θ), with µ as the mean function and θ as model parameters.Source: §2 · p. 2
  • Each arm has a feature vector, and its reward has mean µ(x_i^T θ*), where θ* is unknown.Rewards are drawn independently across arms and rounds from distributions with the specified means.Source: §2 · p. 2
  • The reward noise η_i,t is assumed to be σ²-sub-Gaussian for every arm, round, and λ ≥ 0.Source: §2 · p. 2
  • Maximizing expected cumulative reward over n rounds is equivalent to minimizing expected n-round regret.Source: §2 · p. 2

3 Algorithms

Both algorithms initially explore, then choose arms greedily using randomized parameter estimates. GLM-TSL randomizes through a Laplace posterior approximation; GLM-FPL perturbs past rewards before fitting a GLM.

3 Algorithms

  • After τ initial exploration rounds, the algorithms select an arm maximizing its feature-vector score under a randomized parameter estimate.Any tie among maximizing arms may be broken arbitrarily.Source: §3 · p. 2

3.1 Algorithm GLM-TSL

  • GLM-TSL samples its randomized parameter from a Laplace approximation to the posterior and has regret ˜O(d√n log K) for K arms.The cited prior result gave ˜O(d^(3/2)√n) regret in the infinite-arm setting.Source: §3.1 · p. 2

3.2 Algorithm GLM-FPL

  • GLM-FPL computes a randomized MLE from past rewards perturbed by independent, resampled Gaussian noise, achieving ˜O(d√n log K) regret under an additional arm-feature assumption.The perturbation shifts the log-likelihood gradient while leaving the Hessian positive semi-definite; the method is distinct from posterior sampling in GLMs and can extend to neural networks.Source: §3.2 · p. 3

3.3 Computationally-Efficient Implementations

  • IRLS can compute the MLEs, and aggregating repeated feature vectors allows counts and reward sums to be updated incrementally.Adding N(0, a²) noise per reward is equivalent to adding N(0, N_x a²) noise to each feature vector's reward sum.Source: §3.3 · p. 3
  • Arm selection can be computed efficiently even for infinite arm spaces, but the MLE generally cannot be computed efficiently independently of the round.The passage identifies Jun et al. [2017] as the prior-algorithm exception and notes that the paper studies one approximation empirically.Source: §3.3 · p. 3

4 Analysis

The analysis handles challenges specific to GLMs by relating model fits to log-likelihood derivatives and controlling parameter estimates through initial exploration. It proves matching-order regret bounds for GLM-TSL and GLM-FPL, while the latter’s analysis requires a restriction on arm features.

4.1 Technical Challenges

  • GLM solutions lack closed forms, but their analysis can use the gradient and Hessian of the log likelihood.The paper identifies this as a key idea in earlier GLM-bandit analyses [Filippi et al., 2010, Li et al., 2017].Source: §4.1 · p. 3

4.2 Outline of Our Analyses

  • The analysis bounds regret by controlling how close the estimates are to the true parameter and to each other, and whether the randomized estimate is optimistic.The authors identify bounding two probabilities in their general regret lemma as the hardest part; the perturbation-based probability bounds are described as novel.Source: §4.2 · p. 4

4.3 Analysis of GLM-TSL

  • GLM-TSL’s proof controls bad-event probabilities, tunes the perturbation parameter, and chooses initial exploration so the estimate is likely close to the true parameter.The theorem is stated as a ˜O(d√n log K) regret bound.Source: §4.3 · pp. 4–5

4.3 Analysis of GLM-TSL; 4.4 Analysis of GLM-FPL

4.4 Analysis of GLM-FPL

  • GLM-FPL’s analysis assumes each arm feature has at most one non-zero entry and uses initial exploration to control both the ordinary and randomized estimates.It proves the same ˜O(d√n log K) regret rate as GLM-TSL.Source: §4.4 · p. 5

4.5 Discussion

  • GLM-FPL’s regret bound has worse constant factors than GLM-TSL’s and requires more initial exploration rounds.The suggested a = O(√d log n) is described as too conservative in practice for both algorithms; the paper also experiments with a = O(1).Source: §4.5 · p. 6
  • The GLM-FPL feature assumption makes the relevant matrices share eigenvectors; removing that assumption is left for future work.Without it, the analysis says the matrices may have different eigenvectors and rotations make their relation difficult.Source: §4.5 · p. 6

5 Experiments

The experiments evaluate GLM-TSL and GLM-FPL in logistic bandits, then test GLM-FPL with neural-network reward models on contextual bandits. The reported results favor randomized exploration in both settings, with DeepFPL outperforming the compared alternatives.

5.1 Logistic Bandit

  • The logistic-bandit experiment uses 100 arms, feature dimensions from 5 to 20, a 50,000-round horizon, and 100 randomly generated instances.The evaluated algorithms include GLM-TSL, GLM-FPL, GLM-UCB, and UCB-GLM, with theory-suggested and informal designs.Source: §5.1 · p. 6
  • In logistic bandits, informal GLM-TSL and GLM-FPL have sublinear regret, while informal GLM-UCB and UCB-GLM have linear regret.Theory GLM-TSL and GLM-FPL outperform theory GLM-UCB, but not theory UCB-GLM; the authors report state-of-the-art performance for the randomized algorithms. Figure 1 distinguishes theory-suggested (solid) from informal (dotted) designs.Source: §5.1 · p. 7, Figure 1 · p. 7

5.2 Deep Bandit

  • The contextual-bandit experiments use MNIST and Fashion MNIST, with 500 instances per dataset and 10,000 rounds.Each round presents 10 random examples as arms; rewards are sampled as Bernoulli variables with means 0.75 for the target class and 0.25 otherwise.Source: §5.2 · p. 7
  • DeepFPL applies GLM-FPL's perturbed-reward approach to a neural network, and is compared with DeepFL and repGLM-FPL.DeepFPL perturbs training rewards with independent Gaussian noise; repGLM-FPL first learns a representation during initial random exploration, then applies GLM-FPL to embedded features.Source: §5.2 · p. 7
  • DeepFPL achieves average rewards of at least 0.5 on both datasets, outperforming DeepFL and all repGLM-FPL variants.The reported comparisons are in Figure 2; the best repGLM-FPL exploration setting varies by problem, while DeepFPL needs no such tunable parameter.Source: §5.2 · p. 7, Figure 2 · p. 8
  • The authors report that GLM-FPL generalizes to complex models and works well, while noting that regret guarantees are not established for these models.The experiments use neural networks on high-dimensional classification problems.Source: §5.2 · pp. 7–8

6 Related Work

The related-work discussion contrasts GLM-TSL's regret guarantees with prior bounds and positions GLM-FPL as the first frequentist regret analysis for Gaussian perturbations in a nonlinear model. It also describes posterior-sampling challenges and the feature restriction in the GLM-FPL analysis.

6 Related Work

  • Prior GLM-TSL work in the infinite-arm setting gives a bound that the paper improves, while Dong et al. [2019] analyze Bayes regret only for logistic bandits under stronger feature and parameter assumptions.The paper notes that Dong et al.'s bound does not depend on μ̇_min.Source: §6 · p. 8
  • GLM-TSL has a regret bound that improves on Abeille and Lazaric [2017] in the finite-arm setting and matches their result in the infinite-arm setting.The paper also states that its bound matches most non-randomized GLM bandit bounds up to a factor of √log K.Source: §6 · p. 8
  • GLM-FPL's regret bound assumes each arm feature vector has at most one non-zero entry, and is the first frequentist bound for Gaussian-noise exploration in a nonlinear model.Under this restriction, the analysis still covers 2d potentially optimal arms; the authors leave the more general analysis for future work.Source: §6 · p. 8
  • Posterior approximations in bandits can be computationally costly and lack regret guarantees, motivating the paper's analysis of randomized GLM algorithms.The discussion notes that extending Thompson sampling to nonlinear problems is difficult.Source: §6 · p. 8
  • GLM-FPL uses additive Gaussian noise in a GLM, unlike the earlier logistic-bandit method of Kveton et al. [2019b], which perturbs history with Bernoulli noise and was not analyzed.The paper also relates GLM-FPL to follow-the-perturbed-leader [Hannan, 1957, Kalai and Vempala, 2005] and randomized least-squares value iteration.Source: §6 · p. 8

7 Conclusions

The paper concludes that GLM-TSL and GLM-FPL use randomized perturbations of the maximum likelihood estimate and have the stated regret guarantee. Its experiments support their performance in logistic bandits and GLM-FPL's use with more complex models, while analysis beyond GLM bandits remains future work.

7 Conclusions

  • GLM-TSL and GLM-FPL explore by perturbing the maximum likelihood estimate and have n-round regret bounded by ˜O(d√n log K).The conclusion describes both algorithms as randomized approaches for GLM bandits.Source: §7 · p. 8
  • Both algorithms perform well empirically in logistic bandits, and GLM-FPL is easily generalized to more complex problems.The neural-network experiments are described as encouraging and suggest analysis beyond GLM bandits as future work.Source: §7 · p. 8
  • The analysis assumes arm feature vectors are fixed over time, though the paper says this assumption can be lifted by changing the treatment of the initial exploration-round count.That count becomes a random variable; the authors say they can reuse Li et al. [2017]'s result to analyze it.Source: §7 · p. 8

A Regret Bounds

The appendix presents regret-bound theorems for GLM-TSL and GLM-FPL and develops proof steps for randomized choices based on the history. Its argument also uses undersampled arms and event-based bounds.

A Regret Bounds

  • A lemma bounds the expected per-round regret for randomized algorithms that choose a perturbed solution as a function of the history.The proof proceeds through event-based inequalities and probability bounds.Source: A Regret Bounds · pp. 11–12
  • The proof identifies undersampled arms and selects the least uncertain among them for its argument.It distinguishes undersampled arms from sufficiently sampled arms using the sample covariance matrix.Source: A Regret Bounds · p. 11
  • The appendix states regret-bound theorems for both GLM-TSL and GLM-FPL.The supplied theorem passages identify the bounds but do not provide a complete readable expression.Source: A Regret Bounds · p. 12

B Technical Lemmas

This section extends a self-normalized martingale concentration result and applies it to confidence bounds for GLM parameter estimates. It also bounds the deviation introduced by GLM-FPL’s randomized perturbations.

B Technical Lemmas

  • The extended martingale result applies to a “nice” triplet and an F-stopping time τ that is almost surely no earlier than τ0, with probability at least 1 − δ.Here, τ0 is the first time Vt ⪰ V; the result extends the concentration argument of Abbasi-Yadkori et al. [2011].Source: B Technical Lemmas · p. 13
  • After a round τ with λmin(Gτ) ≥ 1, the argument bounds the estimation error ∥θ̄t − θ*∥2 by 1 with probability at least 1 − 1/n for t ≥ τ.The bound follows by combining the concentration claim with the stated determinant and design-matrix conditions.Source: B Technical Lemmas · pp. 13–14
  • For GLM-FPL, the resampled Gaussian perturbation U has distribution N(0, a²Id) given Ft−1 and norm at most a√(2 log n) with probability at least 1 − 1/n.Combining this bound with (14) yields ∥θ̃t − θ̄t∥2 ≤ 1/2 with probability at least 1 − 1/n under the stated condition.Source: B Technical Lemmas · p. 15
Loading 1906.08947v3…