Dynamic Programming: from Local Optimality to Global Optimality

Speaker: Dr Jingni Yang

Affiliation: University of Sydney

Location: Level 6 Boardroom (629), Colin Clark Building (#39), St Lucia Campus

Abstract: In the theory of dynamic programming, an optimal policy is a policy whose lifetime value dominates that of all other policies from every possible initial condition in the state space. This raises a natural question: when does optimality from a single state imply optimality from every state? We show in a very general setting that irreducibility of the transition kernel is sufficient for this property. Our results have significant implications for modern policy-based algorithms used to solve large-scale dynamic programs in reinforcement learning and other fields.