Beyond No Regret: Instance-Dependent PAC Reinforcement Learning. (arXiv:2108.02717v2 [cs.LG] UPDATED)

Web: http://arxiv.org/abs/2108.02717

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 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 …

arxiv learning lg reinforcement reinforcement learning