mlsanityData to 14 Oct 2026

Representative Action Selection for Large Action Space: From Bandits to MDPs

arXiv 2511.22104 ↗First posted 27 Nov 2025cs.LG math.OC math.PRcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study the problem of selecting a small, representative action subset from an extremely large action space shared across a family of reinforcement learning (RL) environments -- a fundamental challenge in applications like inventory management and recommendation systems, where direct learning over the entire space is intractable. Our goal is to identify a fixed subset of actions that, for every environment in the family, contains a near-optimal action, thereby enabling efficient learning without exhaustively evaluating all actions. This work extends our prior results for meta-bandits to the more general setting of Markov Decision Processes (MDPs). We prove that our existing algorithm achieves performance comparable to using the full action space. This theoretical guarantee is established under a relaxed, non-centered sub-Gaussian process model, which accommodates greater environmental heterogeneity. Consequently, our approach provides a computationally and sample-efficient solution for large-scale combinatorial decision-making under uncertainty.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 18 of its 38 references that are in the map. First posted on arXiv 27 Nov 2025.

Builds on

18 of 38 references.

References · 18

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,897
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2015Policy Distillationcited by 440
  4. 2019Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variablescited by 389
  5. 2015Contextual Markov Decision Processescited by 220
  6. 2015The Benefit of Multitask Representation Learningcited by 195
  7. 2021Multi-Task Reinforcement Learning with Context-based Representationscited by 174
  8. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 70
  9. 2013A PAC-Bayesian bound for Lifelong Learningcited by 69
  10. 2017Near Optimal Behavior via Approximate State Abstractioncited by 66
  11. 2023Advances and Challenges in Meta-Learning: A Technical Reviewcited by 65
  12. 2021Generalization Bounds For Meta-Learning: An Information-Theoretic Analysiscited by 45
6 more
  1. 2021Block Contextual MDPs for Continual Learningcited by 25
  2. 2014A chain rule for the expected suprema of Gaussian processescited by 13
  3. 2024More Flexible PAC-Bayesian Meta-Learning by Learning Learning Algorithmscited by 11
  4. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  5. 2022Reward-Free Policy Space Compression for Reinforcement Learningcited by 6
  6. 2025From Parameters to Behaviors: Unsupervised Compression of the Policy Spacecited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
  2. 2026Learning Markov Decision Processes under Fully Bandit Feedback
  3. 2023Stepsize Learning for Policy Gradient Methods in Contextual Markov Decision Processes
  4. 2025Reinforcement learning with combinatorial actions for coupled restless bandits
  5. 2024How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach
  6. 2025Model-Based Exploration in Monitored Markov Decision Processes
  7. 2024Model-Free Active Exploration in Reinforcement Learning
  8. 2025Where to Intervene: Action Selection in Deep Reinforcement Learning