Markov Decision Processes (MDPs) Recap

As introduced, Reinforcement Learning often deals with sequential decision-making problems. The standard mathematical framework used to model these problems is the Markov Decision Process (MDP). If you've encountered RL before, you'll recognize MDPs as the bedrock upon which most algorithms are built. Let's quickly refresh our understanding of its core components.

An MDP formally describes the environment an RL agent interacts with. It assumes the environment is fully observable and satisfies the Markov property: the future state depends only on the current state and action, not on the sequence of states and actions that preceded it.

An MDP is typically defined by a tuple containing five elements: $(S, A, P, R, \gamma)$.

1. Set of States ($S$)

This is the set of all possible situations the agent can find itself in. States encapsulate all the necessary information about the environment relevant to the decision-making process. For example, in a chess game, the state would be the configuration of all pieces on the board. In a robot navigation task, the state might be the robot's coordinates $(x, y)$ and orientation. State spaces can be:

• Finite: A limited number of distinct states (like in Tic-Tac-Toe or a small grid world). Tabular methods often work well here.
• Infinite or Continuous: An unbounded or continuous range of situations (like robot joint angles or stock market prices). This is where function approximation becomes essential.

2. Set of Actions ($A$)

This is the set of all possible actions the agent can take. The available actions might depend on the current state, sometimes denoted as $A(s)$. Like states, action spaces can be:

• Discrete: A finite set of choices (e.g., 'up', 'down', 'left', 'right' in a grid, or 'buy', 'sell', 'hold' in trading).
• Continuous: A range of action values (e.g., the steering angle of a self-driving car or the amount of thrust for a rocket engine). Value-based methods like Q-learning struggle with continuous actions, motivating policy-based approaches.

3. Transition Probability Function ($P$)

This function defines the dynamics of the environment. It specifies the probability of transitioning to a new state $s'$ after the agent takes action $a$ in state $s$. It's written as: $P(s' | s, a) = \Pr(S_{t+1} = s' | S_t = s, A_t = a)$ This probability distribution captures the stochasticity or uncertainty inherent in the environment's response to the agent's actions. The Markov property is embedded here: the next state $s'$ only depends on the current state $s$ and action $a$.

4. Reward Function ($R$)

The reward function defines the goal of the RL problem. It specifies the immediate numerical reward $r$ the agent receives after taking action $a$ in state $s$ and transitioning to state $s'$. It can be defined in slightly different ways, often as:

• $R(s, a, s')$: Reward depends on the starting state, action taken, and resulting state.
• $R(s, a)$: Reward depends only on the state and action.

The agent's objective is to maximize the cumulative reward over time, not just the immediate reward. Rewards guide the learning process, indicating which actions lead to desirable outcomes.

5. Discount Factor ($\gamma$)

The discount factor $\gamma$ is a value between 0 and 1 ($0 \le \gamma \le 1$) that determines the present value of future rewards. A reward received $k$ steps in the future is discounted by a factor of $\gamma^k$.

• If $\gamma = 0$, the agent is purely "myopic," only caring about the immediate reward.
• If $\gamma$ is close to 1, the agent is "farsighted," valuing future rewards almost as much as immediate ones.

The discount factor ensures that the total expected reward remains finite in continuing tasks (tasks without a terminal state) and allows us to mathematically handle infinite sequences of rewards.

The MDP Interaction Cycle

The interaction between the agent and the environment within an MDP framework follows a cycle:

1. The agent observes the current state $s_t \in S$.
2. Based on $s_t$, the agent selects an action $a_t \in A(s_t)$ according to its policy $\pi(a|s)$.
3. The environment transitions to a new state $s_{t+1}$ based on the transition probability $P(s_{t+1} | s_t, a_t)$.
4. The environment provides a reward $r_{t+1}$ to the agent based on the reward function $R(s_t, a_t, s_{t+1})$.
5. The cycle repeats from the new state $s_{t+1}$.

The basic interaction loop in a Markov Decision Process. The agent observes a state, takes an action, and the environment responds with a new state and a reward.

Understanding this formal structure is necessary because RL algorithms are essentially methods for finding optimal policies within MDPs. When we discuss Q-learning, DQN, Policy Gradients, and Actor-Critic methods, they are all operating under the assumption that the problem can be modeled, at least approximately, as an MDP. The limitations of tabular methods, which we'll touch on next, arise when the components of this tuple, particularly the state and action spaces, become too large or complex to handle explicitly.