# Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 54 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Builds on (most cited first, 30 of 35)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [A Review of Deep Reinforcement Learning for Smart Building Energy Management](https://mlsanity.com/paper/2008.05074/) (2020)
- [Q-learning with Nearest Neighbors](https://mlsanity.com/paper/1802.03900/) (2018)
- [Variance Reduction for Reinforcement Learning in Input-Driven Environments](https://mlsanity.com/paper/1807.02264/) (2018)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [Fast Rates for the Regret of Offline Reinforcement Learning](https://mlsanity.com/paper/2102.00479/) (2021)
- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learning](https://mlsanity.com/paper/1806.01584/) (2018)
- [Deep Inventory Management](https://mlsanity.com/paper/2210.03137/) (2022)
- [Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management](https://mlsanity.com/paper/1905.04337/) (2019)
- [Scalable Deep Reinforcement Learning for Ride-Hailing](https://mlsanity.com/paper/2009.14679/) (2020)
- [Adaptive Discretization in Online Reinforcement Learning](https://mlsanity.com/paper/2110.15843/) (2021)
- [An Approximate Dynamic Programming Algorithm for Monotone Value Functions](https://mlsanity.com/paper/1401.1590/) (2014)
- [Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit](https://mlsanity.com/paper/2411.12878/) (2024)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [Reinforcement learning for bandwidth estimation and congestion control in real-time communications](https://mlsanity.com/paper/1912.02222/) (2019)

## Abstract (arXiv)

Exogenous MDPs (Exo-MDPs) capture sequential decision-making where uncertainty comes solely from exogenous inputs that evolve independently of the learner's actions. This structure is especially common in operations research applications such as inventory control, energy storage, and resource allocation, where exogenous randomness (e.g., demand, arrivals, or prices) drives system behavior. Despite decades of empirical evidence that greedy, exploitation-only methods work remarkably well in these settings, theory has lagged behind: all existing regret guarantees for Exo-MDPs rely on explicit exploration or tabular assumptions. We show that exploration is unnecessary. We propose Pure Exploitation Learning (PEL) and prove the first general finite-sample regret bounds for exploitation-only algorithms in Exo-MDPs. In the tabular case, PEL achieves widetildeO(H2|Xi|√K). For large, continuous endogenous state spaces, we introduce LSVI-PE, a simple linear-approximation method whose regret is polynomial in the feature dimension, exogenous state space, and horizon, independent of the endogenous state and action spaces. Our analysis introduces two new tools: counterfactual trajectories and Bellman-closed feature transport, which together allow greedy policies to have accurate value estimates without optimism. Experiments on synthetic and resource-management tasks show that PEL consistently outperforming baselines. Overall, our results overturn the conventional wisdom that exploration is required, demonstrating that in Exo-MDPs, pure exploitation is enough.