Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
We address policy optimization for adversarial episodic tabular MDPs with bandit feedback, where existing methods suffer from a horizon-dependent gap in regret bounds compared to occupancy-measure approaches. By employing regularized Q-functions, we achieve stability across state-action pairs, closing this gap and yielding improved high-probability regret bounds of $\widetilde O(\sqrt{HS(H+A)T})$ for known transitions and $\widetilde O(HS\sqrt{AT})$ for unknown transitions, matching the state-of-the-art for the latter. This approach is further extended to adversarial linear-mixture MDPs with similar horizon improvements.
Policy optimization for adversarial MDPs now matches state-of-the-art regret bounds by stabilizing local updates with regularized Q-functions, eliminating the horizon gap.
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.