pipette
ENEnglish

Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

Mingyi Li, Taira Tsuchiya

Preprint

En palabras de los autores

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 than those of occupancy-measure-based algorithms. We close this gap by using regularized -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 for known transitions and for unknown transitions, where is the number of states, the number of actions, and the number of episodes. Both bounds improve the horizon dependence of existing policy optimization bounds, and the latter matches the best-known bound. We further extend the algorithm to adversarial linear-mixture MDPs and obtain the same improvement in the horizon dependence.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 17 pages, 2 tables