Markov Decision Processes Formulation Review

As we prepare to study advanced reinforcement learning techniques, it's essential to revisit the mathematical foundation upon which nearly all RL algorithms are built: the Markov Decision Process (MDP). An MDP provides a formal framework for modeling sequential decision-making problems where outcomes are partly random and partly under the control of a decision-maker, or agent.

Think of an agent interacting with an environment over a sequence of discrete time steps $t = 0, 1, 2, ...$. At each step $t$, the agent observes the environment's state $S_t$, selects an action $A_t$, receives a scalar reward $R_{t+1}$, and transitions to a new state $S_{t+1}$. The MDP formalizes this interaction.

A standard MDP is defined by a tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:

States ($\mathcal{S}$)

The set of all possible states the environment can be in. A state $s \in \mathcal{S}$ should ideally capture all relevant information about the environment needed to make an optimal decision. States can range from simple, discrete representations (like positions on a chessboard) to complex, high-dimensional, continuous vectors (like pixel values from a camera feed or joint angles of a robot). In this advanced course, we will frequently deal with large or continuous state spaces where function approximation becomes necessary.

Actions ($\mathcal{A}$)

The set of all possible actions the agent can take. Similar to states, actions $a \in \mathcal{A}$ can be discrete (like 'up', 'down', 'left', 'right' in a grid world) or continuous (like the amount of torque to apply to a motor). The specific set of actions available might depend on the current state $s$, denoted as $\mathcal{A}(s)$.

Transition Dynamics ($P$)

The transition probability function defines the dynamics of the environment. It specifies the probability of transitioning to a state $s'$ and receiving reward $r$ given that the agent was in state $s$ and took action $a$. This is often written as $p(s', r | s, a)$:

$$p(s', r | s, a) = \text{Pr}\{S_{t+1} = s', R_{t+1} = r | S_t = s, A_t = a\}$$

Sometimes, the transition probability is defined purely over states, $P(s' | s, a) = \sum_{r} p(s', r | s, a)$, with the reward function handled separately.

A defining characteristic of an MDP is the Markov Property. This property states that the future state $S_{t+1}$ and reward $R_{t+1}$ depend only on the current state $S_t$ and the action $A_t$, not on the entire history of previous states and actions. Mathematically:

$$\text{Pr}\{S_{t+1} = s', R_{t+1} = r | S_t, A_t, S_{t-1}, A_{t-1}, ..., S_0, A_0\} = \text{Pr}\{S_{t+1} = s', R_{t+1} = r | S_t, A_t\}$$

The current state $S_t$ is assumed to encapsulate all necessary information from the past. While real-world problems might not perfectly adhere to this, the MDP framework is often a powerful and effective approximation.

Reward Function ($R$)

The reward function specifies the immediate numerical feedback the agent receives. It can be defined in several ways, often as the expected immediate reward upon transitioning from state $s$ after taking action $a$:

$$r(s, a) = \mathbb{E}[R_{t+1} | S_t = s, A_t = a] = \sum_{r} r \sum_{s'} p(s', r | s, a)$$

Alternatively, it might depend on the resulting state $s'$ as well: $r(s, a, s') = \mathbb{E}[R_{t+1} | S_t = s, A_t = a, S_{t+1} = s']$. The reward signal $R_{t+1}$ is fundamental; it defines the goal of the RL problem. The agent's objective is derived from maximizing the cumulative sum of these rewards over time.

Discount Factor ($\gamma$)

The discount factor $\gamma$ is a scalar between 0 and 1 ($0 \le \gamma \le 1$). It determines the present value of future rewards. A reward received $k$ time steps in the future is worth only $\gamma^{k-1}$ times what it would be worth if received immediately.

• If $\gamma = 0$, the agent is 'myopic', only caring about maximizing the immediate reward $R_{t+1}$.
• As $\gamma$ approaches 1, the agent becomes more 'farsighted', taking future rewards into account more strongly. The discount factor ensures that the total cumulative reward remains finite in continuing tasks (tasks without a terminal state) and mathematically simplifies analyses.

Policy ($\pi$)

An agent's behavior is defined by its policy, $\pi$. A policy is a mapping from states to probabilities of selecting each possible action. If the agent is in state $s$ at time $t$, then $\pi(a|s)$ is the probability that $A_t = a$. Reinforcement learning methods aim to find a policy that maximizes the expected cumulative reward.

The Goal: Maximizing Return

The agent's objective is to maximize the expected return, which is the cumulative sum of discounted rewards starting from time step $t$. The return $G_t$ is defined as:

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

The core task in RL is to find a policy $\pi$ that maximizes the expected return $\mathbb{E}[G_t]$ from each state $s$. To achieve this, we often estimate value functions, which quantify the expected return from a state ($V^\pi(s)$) or a state-action pair ($Q^\pi(s, a)$) when following policy $\pi$. We will examine these value functions and the equations that govern them (the Bellman equations) in the next section.

Understanding this MDP formulation, its components, and the underlying Markov assumption is the starting point for developing and analyzing the advanced RL algorithms covered in this course. Even when dealing with complex deep learning models, large state/action spaces, or multi-agent scenarios, these fundamental concepts remain central.