Timezone: »

 
Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection
Matteo Papini · Andrea Tirinzoni · Aldo Pacchiano · Marcello Restelli · Alessandro Lazaric · Matteo Pirotta

@
in Workshop on Reinforcement Learning Theory »

We study the role of the representation in finite-horizon Markov Decision Processes (MDPs) with linear structure. We provide a necessary condition for achieving constant regret in any MDP with linear reward representation (even with known dynamics). This result encompasses the well-known scenario of low-rank MDPs and, more generally, zero inherent Bellman error. We demonstrate that this condition is not only necessary but also sufficient for these classes, by deriving a constant regret bound for two optimistic algorithms. As far as we know, this is the first constant regret result for MDPs. Finally, we study the problem of representation selection showing that our proposed algorithm achieves constant regret when one of the given representations is "good". Furthermore, our algorithm can combine representations and achieve constant regret also when none of the representations would.

Author Information

Matteo Papini (Universitat Pompeu Fabra)
Andrea Tirinzoni (Inria)
Aldo Pacchiano (UC Berkeley)
Marcello Restelli (Politecnico di Milano)
Alessandro Lazaric (Facebook AI Research)
Matteo Pirotta (Facebook AI Research)

More from the Same Authors