Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions
arXiv stat.ML1mo4 min read
arXiv:2606.31769v1 Announce Type: cross Abstract: 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 un
