Markov decision process

A Markov decision process (MDP) is the formal description of a problem that reinforcement learning solves. It has five parts:

symbol	meaning
$S$	the set of states, such as every possible pose and velocity of the body
$A$	the set of actions, such as every possible set of motor targets
$P(s' \mid s, a)$	the chance of reaching state $s'$ after taking action $a$ in state $s$
$R(s, a)$	the reward for taking action $a$ in state $s$
$\gamma$	the discount factor, between 0 and 1

The Markov property

“Markov” means the next state depends only on the current state and action, not on how you got there. The present contains everything you need to know. In a physics simulation this is true if the state includes positions and velocities: knowing where the body is and how fast each part is moving is enough to predict the next moment.

In practice the agent often sees only part of the state, through its observation. That is why the observation in this project includes the previous actions and the filter state: without them, the agent couldn’t tell what its own action filter was about to do.

Return and the discount factor

The return is the total reward from a time step onward, with each later reward multiplied by one more factor of $\gamma$:

$$G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots = \sum_{k=0}^{\infty} \gamma^k r_{t+k}$$

The discount factor sets how far ahead the agent cares. A reward $k$ steps away is worth $\gamma^k$ of a reward now, so the agent’s horizon is roughly $1/(1-\gamma)$ steps. With $\gamma = 0.99$ that is 100 steps. At 50 decisions a second, that is about 2 seconds, which is long enough to link a shove to the fall it causes.

In this project

We use $\gamma = 0.99$. The same number appears in the reward shaping term $F = 0.99\,\varphi(s') - \varphi(s)$, because potential-based shaping must use the same discount as the MDP to leave the best policy unchanged.