Lecture Notes on Partially Known MDPs

In these notes we will tackle the problem of finding optimal policies for Markov decision processes (MDPs) which are not fully known to us. Our intention is to slowly transition from an offline setting to an online (learning) setting. Namely, we are moving towards reinforcement learning. As a reminder, a (stationary) MDP M is a 4-tuple (S,A,P,r) where: - S is a finite set of states, - A is a finite set of actions. For intuition, this is just a graph-based way of saying that the reachable part of the Markov chain induced by the policy has a single closed communicating class. Let M be a communicating MDP and i one of its states.