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

arXiv: https://arxiv.org/abs/2511.22104 · HTML: https://mlsanity.com/paper/2511.22104/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 18 of 18)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Policy Distillation](https://mlsanity.com/paper/1511.06295/) (2015)
- [Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variables](https://mlsanity.com/paper/1903.08254/) (2019)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [The Benefit of Multitask Representation Learning](https://mlsanity.com/paper/1505.06279/) (2015)
- [Multi-Task Reinforcement Learning with Context-based Representations](https://mlsanity.com/paper/2102.06177/) (2021)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [A PAC-Bayesian bound for Lifelong Learning](https://mlsanity.com/paper/1311.2838/) (2013)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Advances and Challenges in Meta-Learning: A Technical Review](https://mlsanity.com/paper/2307.04722/) (2023)
- [Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2109.14595/) (2021)
- [Block Contextual MDPs for Continual Learning](https://mlsanity.com/paper/2110.06972/) (2021)
- [A chain rule for the expected suprema of Gaussian processes](https://mlsanity.com/paper/1411.2635/) (2014)
- [More Flexible PAC-Bayesian Meta-Learning by Learning Learning Algorithms](https://mlsanity.com/paper/2402.04054/) (2024)
- [Going Beyond Linear RL: Sample Efficient Neural Function Approximation](https://mlsanity.com/paper/2107.06466/) (2021)
- [Reward-Free Policy Space Compression for Reinforcement Learning](https://mlsanity.com/paper/2202.11079/) (2022)
- [From Parameters to Behaviors: Unsupervised Compression of the Policy Space](https://mlsanity.com/paper/2509.22566/) (2025)

## 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.