Markov Decision Processes

The 5-Tuple Definition $(S, A, P, R, \gamma)$

                       REINFORCE ENVIRONMENT LOOP
                         ┌──────────────────┐
                 Action  │                  │  State s_{t+1}
               ┌─────────┤   ENVIRONMENT    ├─────────┐
               │ a_t     │                  │ reward r_{t+1}
               ▼         └──────────────────┘         ▼
       ┌─────────┴────────┐                  ┌────────┴─────────┐
       │     AGENT        │                  │     AGENT        │
       │ Policy π(a|s)    │                  │ Value V(s)       │
       └──────────────────┘                  └──────────────────┘

1. State Space $S$: Set of all valid environment states.
2. Action Space $A$: Set of all valid agent actions.
3. Transition Dynamics $P(s' \mid s, a)$: $P(S_{t+1} = s' \mid S_t = s, A_t = a)$.
4. Reward Function $R(s, a, s')$: Scalar feedback signal $R_{t+1} \in \mathbb{R}$.
5. Discount Factor $\gamma \in [0, 1)$: Weighs future rewards relative to immediate rewards.

Cumulative Discounted Return $G_t$

The goal of the agent is to maximize expected cumulative discounted return $G_t$:

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

• $\gamma = 0$: Myopic agent (cares only about immediate next reward $R_{t+1}$).
• $\gamma \to 1$: Far-sighted agent (weighs long-term future rewards heavily).

Say this out loud

"An MDP is a 5-tuple (S, A, P, R, γ) defining sequential decision making under the Markov property: future state s_{t+1} depends strictly on current state s_t and action a_t. The agent optimizes policy π(a|s) to maximize expected cumulative discounted return G_t = ∑ γ^k R_{t+k+1}."

Follow-ups to expect

• What is a Partially Observable MDP (POMDP)? An MDP extension where the agent does not observe true state $s_t$ directly, but receives noisy observation $o_t \sim O(o|s)$, maintaining a probability belief state $b(s)$ over hidden states.
• What is the difference between State-Value V(s) and Action-Value Q(s,a)? $V^\pi(s)$ is expected return starting from state $s$ following policy $\pi$. $Q^\pi(s,a)$ is expected return starting from state $s$, taking explicit action $a$, and thereafter following policy $\pi$.