# Fast Convergence of Policy Regret in Learning Stochastic Optimal Control

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 25 May 2026.

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

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [From Predictive to Prescriptive Analytics](https://mlsanity.com/paper/1402.5481/) (2014)
- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Fast Rates for Contextual Linear Optimization](https://mlsanity.com/paper/2011.03030/) (2020)
- [Fast Rates for the Regret of Offline Reinforcement Learning](https://mlsanity.com/paper/2102.00479/) (2021)
- [Stochastic Optimization Forests](https://mlsanity.com/paper/2008.07473/) (2020)
- [Data-Driven Sample Average Approximation with Covariate Information](https://mlsanity.com/paper/2207.13554/) (2022)
- [Classification-based Approximate Policy Iteration: Experiments and Extended Discussions](https://mlsanity.com/paper/1407.0449/) (2014)
- [Q-Measure-Learning for Continuous State RL: Efficient Implementation and Convergence](https://mlsanity.com/paper/2603.03523/) (2026)

## Abstract (arXiv)

Policy learning in modern operations environments faces a fundamental tension between limited operational data and the large, often continuous, state and action spaces over which good decisions must be identified and deployed. We study value-based policy learning in stochastic optimal control: a greedy policy induced by an estimate of the optimal action-value function Q^* is deployed, and its performance is measured by regret. The empirical success of this approach calls for statistical insight into the structures that enable fast regret convergence. We show that, in continuous action spaces, fast policy learning is induced by three geometric structures: a growth exponent p, which quantifies how quickly Q^* separates suboptimal actions from its maximizers; a margin-mass exponent m, which controls how much deployment mass lies on states with weak growth; and an action-wise regularity exponent q, which measures the smoothness of the Q^*-estimation error across actions. Given a n-1/2-accurate estimator of Q^*, we show that the minimax-optimal policy regret convergence rate is [ widetildeThetaleft( n^-minleftfracp2(p-q),fracm+12mright right), ] up to a logarithmic factor at the boundary between the two regimes. The exponent q is crucial: q>0 yields faster-than-n-1/2 regret. This regime is natural in operations applications. In particular, we verify q>0 under mild regularity conditions in dynamic inventory control and service allocation examples, while the mechanism underlying this fast rate regime extends beyond these settings.