Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs
Ruiquan Huang, Donghao Li, Yingbin Liang, and Jing Yang · Read the Full Paper
An agent might need only a few trials to learn what to do, yet spend hours planning between trials. Can it learn a good policy while keeping both costs low?
TL;DR. Our algorithm, Opt-AC, gives an exploration bonus to actions whose outcomes are still uncertain. The critic estimates how well each action would work under the current policy, and the actor shifts probability toward actions with higher estimates. For low-rank Markov decision processes, we show that these updates learn a near-optimal policy with a polynomial number of interactions and polynomial computation when the underlying supervised learning problems can be solved efficiently.