Timezone: »

 
Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
Andrew Wagenmaker · Kevin Jamieson

Tue Dec 14 09:00 AM -- 10:00 AM (PST) @
in Ecological Theory of Reinforcement Learning: How Does Task Design Influence Agent Learning? »
The theory of reinforcement learning has focused on two fundamental problems: achieving low regret, and identifying $\epsilon$-optimal policies. While a simple reduction allows one to apply a low-regret algorithm to obtain an $\epsilon$-optimal policy and achieve the worst-case optimal rate, it is unknown whether low-regret algorithms can obtain the instance-optimal rate for policy identification. We show that this is not possible---there exists a fundamental tradeoff between achieving low regret and identifying an $\epsilon$-optimal policy at the instance-optimal rate. Motivated by our negative finding, we propose a new measure of instance-dependent sample complexity for PAC tabular reinforcement learning which explicitly accounts for the attainable state visitation distributions in the underlying MDP. We then propose and analyze a novel, planning-based algorithm which attains this sample complexity---yielding a complexity which scales with the suboptimality gaps and the ``reachability'' of a state. We show that our algorithm is nearly minimax optimal, and on several examples that our instance-dependent sample complexity offers significant improvements over worst-case bounds.

Author Information

Andrew Wagenmaker (University of Washington)
Kevin Jamieson (U Washington)

More from the Same Authors