mlsanityData to 14 Oct 2026

Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits

arXiv 2302.06025 ↗First posted 12 Feb 2023stat.ML cs.IT cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

We consider the sequential decision-making problem where the mean outcome is a non-linear function of the chosen action. Compared with the linear model, two curious phenomena arise in non-linear models: first, in addition to the "learning phase" with a standard parametric rate for estimation or regret, there is an "burn-in period" with a fixed cost determined by the non-linear function; second, achieving the smallest burn-in cost requires new exploration algorithms. For a special family of non-linear functions named ridge functions in the literature, we derive upper and lower bounds on the optimal burn-in cost, and in addition, on the entire learning trajectory during the burn-in period via differential equations. In particular, a two-stage algorithm that first finds a good initial action and then treats the problem as locally linear is statistically optimal. In contrast, several classical algorithms, such as UCB and algorithms relying on regression oracles, are provably suboptimal.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 31 of its 81 references that are in the map. First posted on arXiv 12 Feb 2023.

Builds on

31 of 81 references.

References · 31

  1. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 743
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  4. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  5. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  6. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  7. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  8. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  9. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  10. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 114
  11. 2018Dexterous Manipulation with Deep Reinforcement Learning: Efficient, General, and Low-Costcited by 84
  12. 2021Adapting to Misspecification in Contextual Banditscited by 81
19 more
  1. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 79
  2. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  3. 2016Kernel-based methods for bandit convex optimizationcited by 63
  4. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  5. 2020Mirror Descent and the Information Ratiocited by 40
  6. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  7. 2020Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisationcited by 33
  8. 2022On the Complexity of Adversarial Decision Makingcited by 33
  9. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 30
  10. 2014Testing for high-dimensional geometry in random graphscited by 25
  11. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
  12. 2015Multi-scale exploration of convex functions and bandit convex optimizationcited by 20
  13. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  14. 2015Online Nonparametric Regression with General Loss Functionscited by 14
  15. 2022Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regretcited by 14
  16. 2021Bandit Phase Retrievalcited by 12
  17. 2020Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimizationcited by 11
  18. 2021Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificatescited by 7
  19. 2021Minimax Regret for Bandit Convex Optimisation of Ridge Functionscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 4.

7 papers.

  1. 2025Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functionscited by 6
  2. 2025Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Banditscited by 2
  3. 2026Interactive Learning of Single-Index Models via Stochastic Gradient Descentcited by 1
  4. 2026Mixture-Greedy for Online Generative Model Selection: Is UCB Necessary in Diversity-Aware Multi-Armed Bandits?cited by 1
  5. 2026The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimizationcited by 1
  6. 2025Stochastic Adaptive Gradient Descent Without Descentcited by 0
  7. 2026Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regretcited by 0