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

2025/11/27 by Quan Zhou, Shie Mannor, Zhou, Quan +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Probability (math.PR) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2511.22104

openalex publication_date 2025/11/27 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• From Parameters to Behaviors: Unsupervised Compression of the Policy Space
• More Flexible PAC-Bayesian Meta-Learning by Learning Learning Algorithms
• Advances and Challenges in Meta-Learning: A Technical Review
• Reward-Free Policy Space Compression for Reinforcement Learning
• Block Contextual MDPs for Continual Learning
• Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Multi-Task Reinforcement Learning with Context-based Representations
• RL for Latent MDPs: Regret Guarantees and a Lower Bound
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variables
• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Near Optimal Behavior via Approximate State Abstraction
• Policy Distillation
• The Benefit of Multitask Representation Learning
• Contextual Markov Decision Processes
• A PAC-Bayesian bound for Lifelong Learning

Related

• Representative Action Selection for Large Action Space Meta-Bandits
• Exact Reduction of Huge Action Spaces in General Reinforcement Learning
• Contextual Bandits with Large Action Spaces: Made Practical
• Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
• Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping