Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits

AI summary

Overview

Research area: Theoretical machine learning — sequential decision making, specifically contextual bandits, Thompson sampling (TS), and frequentist regret analysis.

Technical level: Advanced. The paper is a theory contribution built on regret bounds, posterior sampling, decoupling coefficients, and Eluder dimensions. There are no experiments.

Scope (1 sentence): The paper introduces FGTS-VA, a variance-aware Feel-Good Thompson Sampling algorithm for contextual bandits with a general reward function class, and proves a variance-dependent regret bound using a newly defined generalized decoupling coefficient.

What This Paper Is About

Standard contextual bandit algorithms achieve worst-case regret bounds that ignore how much noise each individual round actually contains, so they pay the same √T-type price even when rewards are nearly deterministic. A line of variance-aware work fixes this for upper confidence bound (UCB) methods by making regret depend on the per-round noise variances σ_t², but the Thompson sampling side has only one result, LinVDTS (Xu et al., 2023), which is restricted to linear rewards and is suboptimal in the model dimension d. This paper asks whether an FGTS-based algorithm can be built for contextual bandits whose regret is simultaneously optimal in d and variance-dependent, and answers affirmatively.

Key Contributions

1. FGTS-VA, a variance-aware FGTS algorithm for general reward functions. The posterior distribution applies variance-dependent weights η_s to the squared log-likelihood terms and adds a feel-good exploration term λ_t max_{a∈A_t} f(x_t, a) for the current step only. When the setting reduces to standard contextual bandits, FGTS-VA is stated to be the first FGTS-based algorithm that does not require knowledge of the horizon T.

2. A generalized decoupling coefficient. This is a novel extension of the standard decoupling coefficient used in FGTS analysis, obtained by introducing flexible parameters β_t. The paper relates it to other complexity measures, showing it is Õ(d) for linear contextual bandits and that it is bounded by the generalized Eluder dimension (Agarwal et al., 2023) for a general reward function class.

3. A variance-dependent regret guarantee. Equipped with the generalized decoupling coefficient (denoted dc), FGTS-VA achieves expected regret O(√((1 + Σ_{t=1}^T σ_t²) dc log|F|) + dc), where |F| is the cardinality of the function class and T is the number of rounds. For linear contextual bandits this becomes the nearly optimal Õ(d√(Σ_{t=1}^T σ_t²) + d), and in the deterministic case it is Õ(dc), matching the lower bound given by Xu et al. (2023).

4. A hyperparameter design that avoids needing the total variance up front. Setting λ_t = c√(Λ_t)/σ̄_t² (with Λ_t the running sum of squared truncated subgaussian norms) achieves the same regret as using the total Λ, while not requiring Λ at initialization. The truncation σ̄_t = max{σ_t, α} also avoids the action-dependent uncertainty term that prior weighted-regression analyses use, which would be circular here because σ̄_t appears in λ_t before the action a_t is chosen.

Main Findings

• First variance-aware FGTS regret bound. FGTS-VA attains Õ(√(dc · log|F| Σ_{t=1}^T σ_t²) + dc) as stated in the abstract, and O(√((1 + Σ_{t=1}^T σ_t²) dc log|F|) + dc) in expectation in the contributions and Theorem 5.4, where dc is the generalized decoupling coefficient.

• Matches UCB-based bounds in the linear case. For contextual linear bandits, FGTS-VA achieves Õ(d√Λ + d), where Λ = Σ_{t=1}^T σ_t² is the sum of variances. Table 1 lists the same regret for Weighted OFUL+ (Zhou and Gu, 2022) and SAVE (Zhao et al., 2023), both UCB-based.

• Strict improvement over the prior Thompson sampling result. LinVDTS (Xu et al., 2023) has regret Õ(d^1.5 √Λ + d^1.5) — and Õ(d^1.5) in the deterministic case — which is suboptimal in the model dimension d. FGTS-VA is Õ(d√Λ + d) with Õ(d) in the deterministic case.

• Minimax-optimal in the deterministic case. With Λ = 0, the regret is O(dc). Since dc is upper bounded by the generalized Eluder dimension, which reduces to the standard Eluder dimension (Russo and Van Roy, 2013) in the deterministic case, the bound is stated to be minimax-optimal for the general reward function class (Jia et al., 2024). A footnote notes the (1 + Λ) term can be further suppressed by setting α even smaller.

• No horizon knowledge required in the standard setting. When σ_t² = 1 for all t, the regret becomes Õ(√(T · dc · log|F|) + dc), which is Õ(d√T) for linear contextual bandits, and the parameters reduce to η_t = 1 and λ_t = Θ(dc^{-1}√t log|F|). The authors note this shows a Type B posterior (as in Dann et al., 2021, for model-free RL) is applicable to contextual bandits.

• **Complexity-me

Authors’ abstract

Variance-dependent regret bounds have received increasing attention in recent studies on contextual bandits. However, most of these studies are focused on upper confidence bound (UCB)-based bandit algorithms, while sampling based bandit algorithms such as Thompson sampling are still understudied. The only exception is the LinVDTS algorithm (Xu et al., 2023), which is limited to linear reward function and its regret bound is not optimal with respect to the model dimension. In this paper, we present FGTSVA, a variance-aware Thompson Sampling algorithm for contextual bandits with general reward function with optimal regret bound. At the core of our analysis is an extension of the decoupling coefficient, a technique commonly used in the analysis of Feel-good Thompson sampling (FGTS) that reflects the complexity of the model space. With the new decoupling coefficient denoted by $\mathrm{dc}$, FGTS-VA achieves the regret of $\tilde{O}(\sqrt{\mathrm{dc}\cdot\log|\mathcal{F}|\sum_{t=1}^Tσ_t^2}+\mathrm{dc})$, where $|\mathcal{F}|$ is the size of the model space, $T$ is the total number of rounds, and $σ_t^2$ is the subgaussian norm of the noise (e.g., variance when the noise is Gaussian) at round $t$. In the setting of contextual linear bandits, the regret bound of FGTSVA matches that of UCB-based algorithms using weighted linear regression (Zhou and Gu, 2022).