Policy optimization improves decision making in adversarial settings
Closing the Horizon Gap in Policy Optimization for Adversarial MDPs
Machine Learning
Summary
When computers learn to make decisions step-by-step in complex situations, they must plan ahead across many actions. Existing methods for this planning are slower because they consider the entire timeline more than necessary. The authors found a way to speed up this process by carefully controlling how the decision updates happen, reducing unnecessary steps. This leads to better performance in challenging environments where outcomes can change adversarially. Their approach works even when the computer doesn’t initially know how actions affect future states.
What this means in practice
- •For reinforcement learning engineers: Develop reinforcement learning agents that adapt faster with provably lower long-term regret even in adversarial game-like environments.
- •For online decision system designers: Improve online algorithms that must make sequential decisions without full knowledge, reducing errors over time despite adversarial costs.
Authors
Mingyi Li, Taira Tsuchiya
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 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.