Rate-Optimal Policy Optimization for Linear Markov Decision Processes

2023/08/28 by Sherman, Uri, Cohen, Alon, Koren, Tomer +1 · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2308.14642

Abstract

We study regret minimization in online episodic linear Markov Decision Processes, and obtain rate-optimal \widetilde O (√ K) regret where K denotes the number of episodes. Our work is the first to establish the optimal (w.r.t.~K) rate of convergence in the stochastic setting with bandit feedback using a policy optimization based approach, and the first to establish the optimal (w.r.t.~K) rate in the adversarial setup with full information feedback, for which no algorithm with an optimal rate guarantee is currently known.

Cited by

• Greedy Sampling Is Provably Efficient for RLHF

Related

• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
• Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
• Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes
• Learning Adversarial Markov Decision Processes with Delayed Feedback
• Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback