# Oracle-Efficient Reinforcement Learning for Max Value Ensembles

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 27 of its 42 references that are in the map.
- First posted on arXiv 27 May 2024.

## 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, 27 of 27)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Offline Reinforcement Learning with Implicit Q-Learning](https://mlsanity.com/paper/2110.06169/) (2021)
- [dm_control: Software and Tasks for Continuous Control](https://mlsanity.com/paper/2006.12983/) (2020)
- [Successor Features for Transfer in Reinforcement Learning](https://mlsanity.com/paper/1606.05312/) (2016)
- [Randomized Ensembled Double Q-Learning: Learning Fast Without a Model](https://mlsanity.com/paper/2101.05982/) (2021)
- [SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning](https://mlsanity.com/paper/2007.04938/) (2020)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Dropout Q-Functions for Doubly Efficient Reinforcement Learning](https://mlsanity.com/paper/2110.02034/) (2021)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction](https://mlsanity.com/paper/1703.01030/) (2017)
- [d3rlpy: An Offline Deep Reinforcement Learning Library](https://mlsanity.com/paper/2111.03788/) (2021)
- [Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines](https://mlsanity.com/paper/1803.07246/) (2018)
- [Learning to Search Better Than Your Teacher](https://mlsanity.com/paper/1502.02206/) (2015)
- [Discount Factor as a Regularizer in Reinforcement Learning](https://mlsanity.com/paper/2007.02040/) (2020)
- [Ensemble Bootstrapping for Q-Learning](https://mlsanity.com/paper/2103.00445/) (2021)
- [AC-Teach: A Bayesian Actor-Critic Method for Policy Learning with an Ensemble of Suboptimal Teachers](https://mlsanity.com/paper/1909.04121/) (2019)
- [CompoSuite: A Compositional Reinforcement Learning Benchmark](https://mlsanity.com/paper/2207.04136/) (2022)
- [Blending Imitation and Reinforcement Learning for Robust Policy Improvement](https://mlsanity.com/paper/2310.01737/) (2023)
- [Ensemble Reinforcement Learning: A Survey](https://mlsanity.com/paper/2303.02618/) (2023)
- [A Boosting Approach to Reinforcement Learning](https://mlsanity.com/paper/2108.09767/) (2021)
- [OIL: Observational Imitation Learning](https://mlsanity.com/paper/1803.01129/) (2018)
- [Active Policy Improvement from Multiple Black-box Oracles](https://mlsanity.com/paper/2306.10259/) (2023)
- [Robotic Manipulation Datasets for Offline Compositional Reinforcement Learning](https://mlsanity.com/paper/2307.07091/) (2023)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)
- [Actor-Critic based Improper Reinforcement Learning](https://mlsanity.com/paper/2207.09090/) (2022)

## Built on by (most cited first, 1 of 1)

- [Multi-Objective Reinforcement Learning for Large-Scale Tote Allocation in Human-Robot Collaborative Fulfillment Centers](https://mlsanity.com/paper/2602.24182/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) in large or infinite state spaces is notoriously challenging, both theoretically (where worst-case sample and computational complexities must scale with state space cardinality) and experimentally (where function approximation and policy gradient techniques often scale poorly and suffer from instability and high variance). One line of research attempting to address these difficulties makes the natural assumption that we are given a collection of heuristic base or textitconstituent policies upon which we would like to improve in a scalable manner. In this work we aim to compete with the textitmax-following policy, which at each state follows the action of whichever constituent policy has the highest value. The max-following policy is always at least as good as the best constituent policy, and may be considerably better. Our main result is an efficient algorithm that learns to compete with the max-following policy, given only access to the constituent policies (but not their value functions). In contrast to prior work in similar settings, our theoretical results require only the minimal assumption of an ERM oracle for value function approximation for the constituent policies (and not the global optimal policy or the max-following policy itself) on samplable distributions. We illustrate our algorithm's experimental effectiveness and behavior on several robotic simulation testbeds.