mlsanityData to 14 Oct 2026

Is Offline Decision Making Possible with Only Few Samples? Reliable Decisions in Data-Starved Bandits via Trust Region Enhancement

arXiv 2402.15703 ↗First posted 24 Feb 2024cs.LG cs.AI stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

What can an agent learn in a stochastic Multi-Armed Bandit (MAB) problem from a dataset that contains just a single sample for each arm? Surprisingly, in this work, we demonstrate that even in such a data-starved setting it may still be possible to find a policy competitive with the optimal one. This paves the way to reliable decision-making in settings where critical decisions must be made by relying only on a handful of samples. Our analysis reveals that stochastic policies can be substantially better than deterministic ones for offline decision-making. Focusing on offline multi-armed bandits, we design an algorithm called Trust Region of Uncertainty for Stochastic policy enhancemenT (TRUST) which is quite different from the predominant value-based lower confidence bound approach. Its design is enabled by localization laws, critical radii, and relative pessimism. We prove that its sample complexity is comparable to that of LCB on minimax problems while being substantially lower on problems with very few samples. Finally, we consider an application to offline reinforcement learning in the special case where the logging policies are known.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 44 of its 77 references that are in the map. First posted on arXiv 24 Feb 2024.

Builds on

44 of 77 references.

References · 44

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  2. 2021Convex optimizationcited by 2,515
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  4. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,809
  5. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learningcited by 1,427
  6. 2021Offline Reinforcement Learning with Implicit Q-Learningcited by 1,293
  7. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,241
  8. 2019Advantage-Weighted Regression: Simple and Scalable Off-Policy Reinforcement Learningcited by 782
  9. 2019Behavior Regularized Offline Reinforcement Learningcited by 662
  10. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  11. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  12. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
32 more
  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  2. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  3. 2016Optimal Best Arm Identification with Fixed Confidencecited by 239
  4. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 188
  5. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 117
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  7. 2020Batch Value-function Approximation with Only Realizabilitycited by 104
  8. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  9. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 83
  10. 2014Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Armscited by 79
  11. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  12. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  13. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  14. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  15. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 64
  16. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  17. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  18. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  19. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  20. 2022Bootstrapped Transformer for Offline Reinforcement Learningcited by 37
  21. 2021Deep Reinforcement Learning for the Control of Robotic Manipulation: A Focussed Mini-Reviewcited by 36
  22. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  23. 2013Volumetric Spanners: an Efficient Exploration Basis for Learningcited by 24
  24. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  25. 2018Deep Reinforcement Learning for Dynamic Treatment Regimes on Medical Registry Datacited by 23
  26. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  27. 2020Offline Contextual Multi-armed Bandits for Mobile Health Interventions: A Case Study on Emotion Regulationcited by 13
  28. 2022Variance-Aware Sparse Linear Banditscited by 11
  29. 2023Reinforcement Learning Tutor Better Supported Lower Performers in a Math Taskcited by 11
  30. 2022Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiencycited by 10
  31. 2020Variable Selection via Thompson Samplingcited by 7
  32. 2022Policy evaluation from a single path: Multi-step methods, mixing and mis-specificationcited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Offline Local Search for Online Stochastic Bandits
  2. 2026Offline-to-Online Learning in Linear Bandits
  3. 2023Selective Uncertainty Propagation in Offline RL
  4. 2023Offline Reinforcement Learning with Additional Covering Distributions
  5. 2024Robust Offline Policy Learning with Observational Data from Multiple Sources
  6. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  7. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
  8. 2026Unlearning Offline Stochastic Multi-Armed Bandits