Solution to a Markov Decision Process

The reward hypothesis states that the goal of the environment is encoded in the rewards. If you want the agent to learn how to play chess for example you give out a reward of +1 when the agent wins, a reward of -1 when the agent loses and a reward of 0 whenever there is a draw. The goal of the agent is therefore to collect as many rewards as possible.

We can express the same idea mathematically by defining the goal G_t undefined , also called the return, as the sum of rewards from the timestep t+1 undefined to either the terminal state T undefined if we are dealing with episodic tasks or to infinity if we are dealing with continuing tasks.

To demonstrate this idea with a simple example let's once again take the MDP from the previous section. We are dealing with two states and an agent that takes random actions. Whenever the agent lands in the state 1 it receives a reward of 1, other wise it receives a negative reward of -1.

In the example below we calculate the return from the perspective of the initial state G_0 undefined . Each time the agent receives a reward we add the value to the return value.

In order to reduce the value of future rewards we discount each reward, by applying a discount factor \gamma undefined , a value between 0 and 1. The farther away the reward is from the current time step t undefined , the lower its contribution to the return G_t undefined .

The easiest way to illustrate this concept is by thinking about the time value of money. If we have to choose between getting 1000$ now and getting 1000$ in 10 years, we should definetely choose the 1000$ in the present. The money could be invested for a ten year period, such that in 10 years the investor gets back an amout that is larger than 1000$. A reward now is always more valuable thant a future reward.

Discounting is especially important for continuing tasks. If the episode has no natural ending, the return G undefined could theoretically become infinite. Discounted rewards on the other hand approach 0 when they are far into the future.

The interactive example below shows how the discounting rate dependings on the value of the \gamma undefined . The lower the gamma the faster the progression towards 0.

Discount Factor 0.95

The return is very tighly integrated with the strategy thate the agent is following. This strategy is called policy. A better policy will obviously generate better returns and vice versa.

A policy \pi undefined as a mapping from a particular state s undefined to a probability of an action a undefined : \pi{(a \mid s)} = Pr[A_t = a \mid S_t = s] undefined . To take an action in a state the agent simply draws an action from the policy distribution A_t \sim \pi{(. \mid S_t)} undefined .

In the above example we are dealing with 2 possible states and 2 possible actions. We can therefore simply store the policy in a mapping table. In future chapters we will use neural networks for more complex MDPs.

The goal of the agent is to find a policy that maximizes returns, but simply maximizing the return is tricky, because in reinforcement learning we often deal with stochastic policies and environments. That stochasticity produces different trajectories and therefore different returns G_t undefined . But how can we measure how good it is for the agent to use a certain policy \pi undefined if the generated returns are not consistent? By utilizing value functions.

The state-value function v_{\pi}(s) undefined calculates the expected return when the agent is in the state s undefined and follows the policy \pi undefined .

The action-value function q_{\pi}(s, a) undefined calculates the expected return when the agent is the state s undefined , takes the action a undefined at first and then keeps following the policy \pi undefined .

For the time being we do not have the tools to exactly calculate the value function for each state, but we can make an educated guess. Let's take the same Markov decision we have been dealing so far, but only focus on the state 0.

The random policy that we have been using so far is clearly not optimal.

The below agent implements a policy that tends to take the action B more often. This behaviour will generate a higher expected return.

A state-value function allows the agent to assign a goodness value to each of the states for a given policy. Change the policy and observe if you see any improvements. That is where the action-value function comes into play. The action-value function allows us to reason about changing a single action. We can ask the question what would happen if we generally keep the same policy and only change the next action. Would that new policy be more benefitial to us? If yes, maybe we should change our policy. And the goal of the agent is to find the optimal policy.

Optimality implies that there is a way to compare different policies and to determine which of the policies is better. In a Markov decision process value functions are used as a metric of the goodness of a policy. The policy \pi undefined is said to be better than the policy \pi undefined if and only if the value function of \pi undefined is larger or equal to the value function of policy \pi' undefined for all states in the state set \mathcal{S} undefined .

The optimal policy \pi_* undefined is therefore the policy that is better (or at least not worse) than any other policy.

It is not hard to imagine the optimal strategy for the two-states MDP. The agent needs to always take the action B. This policy increases the probability to land in the state 2 and thus increases the probability of getting a reward of 5. In other words always taking the actio B would maximize the value function.

How we can numerically find the optimal policy \pi_* undefined and the corresponding value functions v_* undefined , q_* undefined is going to be the topic of the rest of the reinforcement learning block. The essence of reinforcement learning is to find the optimal policy, given that the environment contains a Markov decision process under the hood.