Summary
A new arXiv paper (2610.12362) by Mingyi Li and Taira Tsuchiya addresses policy optimization for online episodic tabular MDPs with adversarial losses and bandit feedback. While policy optimization updates policies locally at each state—avoiding optimization over the occupancy-measure polytope—its existing regret bounds were worse than occupancy-measure-based algorithms by a factor of the horizon H. The authors close this gap by introducing regularized Q-functions, which jointly control the stability of local updates across all state-action pairs rather than separately at each state. The resulting algorithm achieves high-probability regret bounds of Õ(√(HS(H+A)T)) for known transitions and Õ(HS√(AT)) for unknown transitions, where S is the number of states, A the number of actions, and T the number of episodes. Both bounds improve the horizon dependence of prior policy optimization methods, matching known optimal bounds. The approach also extends to adversarial linear mixture MDPs with the same horizon-dependence improvement.
Paper Overview
Field: Machine Learning
Authors: Mingyi Li, Taira Tsuchiya
Published: 2026-10-08
arXiv: 2610.12362
Original Abstract
We consider policy optimization for online episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback. Policy optimization updates the policy locally at each state and avoids optimization over the occupancy-measure polytope, but its existing regret bounds are larger by a factor of the horizon \(H\) than those of occupancy-measure-based algorithms. We close this gap by using regularized \(Q\)-functions, which allow us to control the stability of the local updates jointly over all state-action pairs rather than separately at each state. The resulting algorithm attains high-probability regret bounds of \(\widetilde O(\sqrt{HS(H+A)T})\) for known transitions and \(\widetilde O(HS\sqrt{AT})\) for unknown transitions, where \(S\) is the number of states, \(A\) the number of actions, and \(T\) the number of episodes. Both bounds improve the horizon dependence of existing policy optimization methods, matching the known optimal bounds. We also extend our algorithm to adversarial linear mixture MDPs with the same improvement in horizon dependence.
---
*Auto-collected on 2026-10-12*
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/178635899