# Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 50 references that are in the map.
- First posted on arXiv 30 Jun 2026.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)

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

- [Closing the Horizon Gap in Policy Optimization for Adversarial MDPs](https://mlsanity.com/paper/2610.12362/) (2026)

## Abstract (arXiv)

We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees together with data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with first-order, second-order, and path-length bounds, but only under known transitions, leaving open whether such data-dependent guarantees are achievable by policy optimization when the transition kernel is unknown. We resolve this by developing a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions. The key ingredient is a new design of optimistic Q-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with the transition-dependent complexity term while simultaneously achieving gap-dependent polylog(T) regret in the stochastic regime.