THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Poster
Contextual Decision Processes with low Bellman rank are PAC-Learnable
Nan Jiang · Akshay Krishnamurthy · Alekh Agarwal · John Langford · Robert Schapire

Tue Aug 01:30 AM -- 05:00 AM PDT @ Gallery #65
in Posters Tue »

This paper studies systematic exploration for reinforcement learning (RL) with rich observations and function approximation. We introduce contextual decision processes (CDPs), that unify most prior RL settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables tractable learning of near-optimal behavior in CDPs and is naturally small for many well-studied RL models. Our second contribution is a new RL algorithm that does systematic exploration to learn near-optimal behavior in CDPs with low Bellman rank. The algorithm requires a number of samples that is polynomial in all relevant parameters but independent of the number of unique contexts. Our approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for RL with function approximation.

Author Information

Nan Jiang (Microsoft Research)
Akshay Krishnamurthy (UMass)
Alekh Agarwal (Microsoft Research)
John Langford (Microsoft Research)
Robert Schapire (Microsoft Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors