Upper Bounds on the Performance of Discretisation in Reinforcement Learning

Abstract

Reinforcement learning is a machine learning framework whereby an agent learns to perform a task by maximising its total reward received for selecting actions in each state. The policy mapping states to actions that the agent learns is either represented explicitly, or implicitly through a value function. It is common in reinforcement learning to discretise a continuous state space using tile coding or binary features. We prove an upper bound on the performance of discretisation for direct policy representation or value function approximation.

Keywords

• Reinforcement learning
• Tile coding
• Performance Bounds
• Average Case Analysis