Asymptotically optimal reinforcement learning in Block Markov Decision Processes

The field of machine learning, and artificial intelligence more broadly, has taken society by storm. One of its key techniques, Reinforcement Learning (RL), is widely applied, e.g., in healthcare, industrial control, and robotics. Despite its promise, RL still faces many practical challenges. Among these is the curse of dimensionality, which makes learning in large state spaces intractable without structure. This is problematic because the state space size is often exponential in the number of system components. Fortunately, many environments do exhibit exploitable structure. For instance, when different states share similar transition probabilities, then we could first learn a clustering of the state space. This reduces its effective size, mitigating the curse of dimensionality's impact.