More Like this

1. Pareto Optimal Model Selection in Linear Bandits

   Zhu, Yinglun; Nowak, Robert D (March 2022, International Conference on Artificial Intelligence and Statistics)

   We study model selection in linear bandits, where the learner must adapt to the dimension (denoted by 𝑑⋆ ) of the smallest hypothesis class containing the true linear model while balancing exploration and exploitation. Previous papers provide various guarantees for this model selection problem, but have limitations; i.e., the analysis requires favorable conditions that allow for inexpensive statistical testing to locate the right hypothesis class or are based on the idea of “corralling” multiple base algorithms, which often performs relatively poorly in practice. These works also mainly focus on upper bounds. In this paper, we establish the first lower bound for the model selection problem. Our lower bound implies that, even with a fixed action set, adaptation to the unknown dimension 𝑑⋆ comes at a cost: There is no algorithm that can achieve the regret bound 𝑂˜(𝑑⋆𝑇‾‾‾‾√) simultaneously for all values of 𝑑⋆ . We propose Pareto optimal algorithms that match the lower bound. Empirical evaluations show that our algorithm enjoys superior performance compared to existing ones. 

   more » « less
2. Learning Neural Contextual Bandits through Perturbed Rewards

   Jia, Yiling; Zhang, Weitong; Zhou, Dongruo; Gu, Quanquan; Wang, Hongning (April 2022, The Tenth International Conference on Learning Representations (ICLR'2022))

   Thanks to the power of representation learning, neural contextual bandit algorithms demonstrate remarkable performance improvement against their classical counterparts. But because their exploration has to be performed in the entire neural network parameter space to obtain nearly optimal regret, the resulting computational cost is prohibitively high. We perturb the rewards when updating the neural network to eliminate the need of explicit exploration and the corresponding computational overhead. We prove that a O(d\sqrt{T}) regret upper bound is still achievable under standard regularity conditions, where $$T$$ is the number of rounds of interactions and $$\tilde{d}$$ is the effective dimension of a neural tangent kernel matrix. Extensive comparisons with several benchmark contextual bandit algorithms, including two recent neural contextual bandit models, demonstrate the effectiveness and computational efficiency of our proposed neural bandit algorithm. 

   more » « less
3. TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation

   Baek, Jackie; Farias, Vivek F (April 2023, PMLR)

   Thompson sampling has become a ubiquitous ap- proach to online decision problems with bandit feedback. The key algorithmic task for Thomp- son sampling is drawing a sample from the pos- terior of the optimal action. We propose an al- ternative arm selection rule we dub TS-UCB, that requires negligible additional computational effort but provides significant performance im- provements relative to Thompson sampling. At each step, TS-UCB computes a score for each arm using two ingredients: posterior sample(s) and upper confidence bounds. TS-UCB can be used in any setting where these two quantities are available, and it is flexible in the number of posterior samples it takes as input. TS-UCB achieves materially lower regret on a comprehen- sive suite of synthetic and real-world datasets, including a personalized article recommendation dataset from Yahoo! and a suite of benchmark datasets from a deep bandit suite proposed in Riquelme et al. (2018). Finally, from a theoreti- cal perspective, we establish optimal regret guar- antees for TS-UCB for both the K-armed and linear bandit models. 

   more » « less
4. Finite dimensional models for extremes of Gaussian and non-Gaussian processes

   H, Xu; M. Grigoriu (January 2022, Probabilistic engineering mechanics)

   Numerical solutions of stochastic problems involving random processes 𝑋(𝑡), which constitutes infinite families of random variables, require to represent these processes by finite dimensional (FD) models 𝑋𝑑 (𝑡), i.e., deterministic functions of time depending on finite numbers 𝑑 of random variables. Most available FD models match the mean, correlation, and other global properties of 𝑋(𝑡). They provide useful information to a broad range of problems, but cannot be used to estimate extremes or other sample properties of 𝑋(𝑡). We develop FD models 𝑋𝑑 (𝑡) for processes 𝑋(𝑡) with continuous samples and establish conditions under which these models converge weakly to 𝑋(𝑡) in the space of continuous functions as 𝑑 → ∞. These theoretical results are illustrated by numerical examples which show that, under the conditions established in this study, samples and extremes of 𝑋(𝑡) can be approximated by samples and extremes of 𝑋𝑑 (𝑡) and that the discrepancy between samples and extremes of these processes decreases with 𝑑. 

   more » « less
5. Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regret Regimes

   https://doi.org/10.1287/opre.2021.2237  

   Hu, Yichun; Kallus, Nathan; Mao, Xiaojie (January 2022, Operations Research)

   We study a nonparametric contextual bandit problem in which the expected reward functions belong to a Hölder class with smoothness parameter β. We show how this interpolates between two extremes that were previously studied in isolation: nondifferentiable bandits (β at most 1), with which rate-optimal regret is achieved by running separate noncontextual bandits in different context regions, and parametric-response bandits (infinite [Formula: see text]), with which rate-optimal regret can be achieved with minimal or no exploration because of infinite extrapolatability. We develop a novel algorithm that carefully adjusts to all smoothness settings, and we prove its regret is rate-optimal by establishing matching upper and lower bounds, recovering the existing results at the two extremes. In this sense, our work bridges the gap between the existing literature on parametric and nondifferentiable contextual bandit problems and between bandit algorithms that exclusively use global or local information, shedding light on the crucial interplay of complexity and regret in contextual bandits. 

   more » « less