Title: Sample-efficient Reinforcement Learning with Rich Observations
Speaker: Alekh Agrarwal, Microsoft Research
Date: Wednesday, November 2, 2016 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
This talk considers a core question in reinforcement learning (RL): How can we tractably solve sequential decision making problems where the learning agent receives rich observations? We begin with a new model called Contextual Decision Processes (CDPs) for studying such problems, and show that it encompasses several prior setups to study RL such as MDPs and POMDPs. Several special cases of CDPs are, however, known to be provably intractable in their sample complexities. To overcome this challenge, we further propose a structural property of such processes, called the Bellman Rank. We find that the Bellman Rank of a CDP (and an associated class of functions) provides an intuitive measure of the hardness of a problem in terms of sample complexity. In particular, we propose an algorithm, whose sample complexity scales with the Bellman Rank of the process, and is completely independent of the size of the observation space of the agent. We also show that our techniques are robust to our modeling assumptions, and make connections to several known results as well as highlight novel consequences of our results.
This talk is based on joint work with Nan Jiang, Akshay Krishnamurthy, John Langford and Rob Schapire.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/