Optimal control in reinforcement learning

David Silver video – Optimal policy theorem!

The core problem of MDPs is to find a policy for the decision maker: a function $\pi$ that specifies the action $\pi(s)$ that the decision maker will choose when in state $s$ (vid). Note that once a Markov decision process is combined with a policy in this way, this fixes the action for each state and the resulting combination behaves like a Markov chain. The policy could be stochastic too. Apparently, no need to have stochastic policies, except when we have multiple agents (studied in Game theory, as strategies), vid.

vid

The goal is to choose a policy $\pi$ that will maximize some cumulative function of the random rewards, typically the expected discounted sum over a potentially infinite horizon:

where we choose $a_t = \pi(s_t)$, $\ \gamma \$ is the discount factor and satisfies $0 \le\ \gamma\ < 1$. (For example, $\gamma = 1/(1+r)$ when the discount rate is r.) $\gamma$ is typically close to 1. This is known as the total payoff, or value function, for policy $\pi$.

The Value functions gives a Partial ordering over policies, given by $\pi_1 \geq \pi_2$ iff $v_{\pi_1} (s) \geq v_{\pi_2}(s)$ for all $s$. Furthermore, one can show that for finite MDPs, there is always an Optimal policy. There may be several optimal policies, but they all share the same Value functions, known as the Optimal value function. The value function satisfies a recursive equation called Bellman optimality equation, which will be used for the learning algorithms that compute the optimal policy.

Because of the Markov property, the optimal policy for this particular problem can indeed be written as a function of $s$ only, as assumed above (although for some richer models this may not be true)

For many algorithms (in particular model-free) one also uses another Value function known as Q function, or action-value function

Undiscounted reward

One can have RL with no discount factor $\gamma$. Approach: average reward MPD.

One can and often does apply plain undiscounted rewards to Episodic MDPs