Learning curve bounds for a Markov decision process with undiscounted rewards
Lawrence K. Saul, Satinder Pal Singh · 1996
The goal of learning in Markov decision processes is to find a policy that yields the maximum expected return over time.In problems with large state spaces, computing these averages directly is not feasible; instead, the agent must estimate them by stochastic exploration of the state space.Using methods from statistical mechanics, we study how the agent's performance depends on the allowed exploration time.In particular, for a simple control problem with undiscounted rewards, we compute a lower bound on the return of policies that appear optimal based on imperfect statistics.This is done in the thermodynamic limit:T ~co, N 4 cO, o = T/A' (finite), where T is the number of time steps allotted per policy evaluation and N is the size of the state space.