Linear Programming Techniques in Reinforcement Learning

This lecture introduces the linear programming (LP) approach to reinforcement learning (RL), presenting it as an alternative convex viewpoint. It begins by revisiting the reinforcement learning setup, emphasizing the challenges faced in traditional methods, such as the need for approximate dynamic programming and the limitations of existing algorithms. The instructor discusses the Bellman optimality equation and its significance in defining optimal policies. The lecture then transitions to the primal and dual formulations of linear programming, detailing how these can be applied to solve Markov decision processes (MDPs). The occupancy measure is defined and visualized, illustrating its role in determining the value function. The lecture also covers the REPS algorithm, which applies proximal point methods to the dual LP, showcasing its effectiveness in practical applications like robotics. The session concludes with a summary of the LP approach's advantages and challenges, setting the stage for future discussions on policy gradient methods.