Markov Decision Process

reinforcement-learning

Definition

Markov Decision Process

A Markov decision process (MDP) is the tuple $(\mathcal{S},\mathcal{A},P,R,\gamma )$ modelling an agent interacting with an environment over discrete time, where the environment’s response satisfies the Markov property.

• $\mathcal{S}$: state space.
• $\mathcal{A}$: action space (or $\mathcal{A}(s)$ when state-dependent).
• $P(s^{\prime }\mid s,a)$: transition probability of reaching $s^{\prime }$ after action $a$ in $s$.
• $R(s,a,s^{\prime })$: immediate reward on transitioning from $s$ to $s^{\prime }$ under $a$.
• $\gamma \in [0,1]$: discount factor.

At step $t$, the agent in state $s_t$ selects $a_t\in \mathcal{A}$ via a policy $\pi (a\mid s)$, then receives $r_{t+1}=R(s_t,a_t,s_{t+1})$ and transitions to $s_{t+1}\sim P(\cdot \mid s_t,a_t)$. The goal is to choose $\pi$ maximising the expected discounted return

$$G_t=\sum _{k=0}^{\infty }{\gamma }^k{r}_{t+k+1}.$$