{"ID":5443796,"CreatedAt":"2026-07-01T02:07:11.383974684Z","UpdatedAt":"2026-07-03T14:41:59.01997188Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31769","arxiv_id":"2606.31769","title":"Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions","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 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 $\\mathrm{polylog}(T)$ regret in the stochastic regime.","short_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...","url_abs":"https://arxiv.org/abs/2606.31769","url_pdf":"https://arxiv.org/pdf/2606.31769v1","authors":"[\"Mingyi Li\",\"Taira Tsuchiya\",\"Kenji Yamanishi\"]","published":"2026-06-30T14:54:34Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}