PAC Bounds for Discounted MDPs
This work provides theoretical guarantees for reinforcement learning algorithms in MDPs, but it is incremental as it builds on prior bounds by generalizing and tightening them.
The paper tackles the problem of learning near-optimal behavior in finite-state discounted Markov Decision Processes (MDPs) by deriving new upper and lower bounds on sample complexity, showing that these bounds match up to logarithmic factors.
We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (MDPs). For the upper bound we make the assumption that each action leads to at most two possible next-states and prove a new bound for a UCRL-style algorithm on the number of time-steps when it is not Probably Approximately Correct (PAC). The new lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors.