Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms
Abstract. An important application of reinforcement learning (RL) is to nite-state control problems and one of the most di cult problems in learning for control is balancing the exploration/exploitation tradeo. Existing theoretical results for RL give very little guidance on reasonable ways to perform exploration. In this paper, we examine the convergence of single-step on-policy RL algorithms for control. On-policy algorithms cannot separate exploration from learning and therefore must confront the exploration problem directly. Weprove convergence results for several related on-policy algorithms with both decaying exploration and persistent exploration. We also provide examples of exploration strategies that can be followed during learning that result in convergence to both optimal values and optimal policies.