Rate-Optimal Policy Optimization for Linear Markov Decision Processes

arXiv:2308.14642v2 Announce Type: replace
Abstract: We study regret minimization in online episodic linear Markov Decision Processes, and obtain rate-optimal $\widetilde O (\sqrt 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 …

abstract arxiv convergence cs.lg decision episodes feedback linear markov optimization policy processes rate stochastic study type work