Markov decision process (MDP)

The agent receives state s_t and reward r_t, then sends action a_t to the environment, which returns the next state s_(t+1) and reward r_(t+1) — [Drawing from Sutton and Barto, Reinforcement Learning: An Introduction, 1998]

An MDP is defined by:

Set of states $S$
Set of actions $A$
Transition function $P (s^{'} | s, a)$
Action noise is encoded in the transition probabilities: the chosen action can lead to different next states.
Reward function $R (s, a, s^{'})$
Start state $s_{0}$
Discount factor $γ$
Horizon $H$

$MDP (S, A, T, R, γ, H)$

goal:

max_{π} E [\sum_{t = 0}^{H} γ^{t} R (S_{t}, A_{t}, S_{t + 1}) | π]

Find the policy that maximizes the expected sum of discounted rewards.

Example: Gridworld

A four-column, three-row Gridworld with Start at (1,1), a wall at (2,2), a robot at (3,1), a plus-one reward at (4,3), and a minus-one reward at (4,2)

Goal:

max_{π} E [\sum_{t = 0}^{H} γ^{t} R (S_{t}, A_{t}, S_{t + 1}) | π]

So, as written, this is not a value function: it does not explicitly condition on $S_{0} = s$ .

$π :$

A robot holds a Gridworld policy map with an action arrow in each nonterminal, unblocked cell