Policy

The rules that determine the agent’s action for each state in an MDP are known as the policy.

This may be stochastic (the policy defines a distribution over actions for each state) or deterministic (the agent always takes the same action in a given state).

• A stochastic policy $\pi [a|s]$ returns a probability distribution over each possible action $a$ for state $s$, from which a new action is sampled.
• A deterministic policy $\pi [a|s]$ returns one for the action $a$ that is chosen for state $s$ and zero otherwise.

A stationary policy depends only on the current state. A non-stationary policy also depends on the time step.

The environment and the agent form a loop. The agent receives the state $s_t$ and reward $r_t$ from the last time step. Based on this, it can modify the policy $\pi [a_t|s_t]$ if desired and choose the next action $a_t$. The environment then advances to the next state according to $Pr(s_{t+1}|s_t,a_t)$ and issues a reward according to $Pr(r_{t+1}|s_t,a_t)$.

Optimal policy

We want a policy that maximizes the return. For MDPs (but not POMDPs), there is is always a deterministic, stationary policy that maximizes the value of every state. If we know this optimal policy, then we get the optimal state-value function $v^{\ast }[s_t]$:

$$v^{\ast }[s_t]=\underset{\pi }{\max }[\mathbb{E}[G_t|s_t,\pi ]]$$

Similarly, the optimal state-action value function is obtained under the optimal policy:

$$q^{\ast }[s_t,a_t]=\underset{\pi }{\max }[\mathbb{E}[G_t|s_t,a_t,\pi ]]$$

Turning this on its head, if we knew the optimal action-values $q^{\ast }[s_t,a_t]$, then we could derive the optimal policy by choosing the action $a_t$ with the highest value:

$$\pi [a_t|s_t]\leftarrow \underset{a_t}{\mathrm{argmax}}[q^{\ast }[s_t,a_t]]$$

• The notation here means set $\pi [a_t|s]$ to one for action $a$ and $\pi [a_t|s]$ to zero for other actions.

Some RL algorithms are based on alternately estimating the action values and policy (Tabular Reinforcement Learning).