PAC Reinforcement Learning with Rich Observations

Understand

We propose and study a new model for reinforcement learning with rich observations, generalizing contextual bandits to sequential decision making.

• These models require an agent to take actions based on observations (features) with the goal of achieving long-term performance competitive with a large set of policies.
• To avoid barriers to sample-efficient learning associated with large observation spaces and general POMDPs, we focus on problems that can be summarized by a small number of hidden states and have long-term rewards that are predictable by a reactive function class.
• In this setting, we design and analyze a new reinforcement learning algorithm, Least Squares Value Elimination by Exploration.