Reinforcement Learning (RL) is fundamentally different from Supervised and Unsupervised Learning. While the latter focus on learning probability distributions like p(y|x) or p(x), RL is about an AI agent learning the ‘optimal’ policy to solve a given problem space, such as controlling a robot or playing StarCraft.
But what exactly does “optimal” mean, and how do we mathematically model this continuous interaction? The answer lies in the Markov Decision Process (MDP) and the fundamental Bellman Equation.
In RL, the agent interacts with an Environment. The agent perceives the environment’s state using a Sensor (percept/observed state) , decides on an Action using a Function (Policy) , and executes it via an Actuator. The environment, in turn, provides a Reward.
The MDP provides the formal, mathematical framework for this interaction:
State: Current description of the environment.
Action: Possible moves the agent can take.
Policy: The agent’s strategy for choosing an action.
Transition: How the environment’s state changes.
Reward: Evaluation of an action (e.g., cost).
The ultimate goal of RL is to learn the policy ($\pi$) that maximizes the accumulated Reward.
A key assumption in the MDP is the Markov Property: the future state s’ only depends on the current state ($s$) and action ($a$).
In a Markovian State Transition Model, the probability of the next state is defined as $P(s’|s, a)$. This property is vital because it allows for a simplified, powerful recursive solution (the Bellman Equation) that doesn’t require considering the entire history of states.
In the Multi-armed Bandit problem (a simplified RL problem without state transitions), the quality of an action Q is the expected reward from that action.
However, in the full MDP, the reward r doesn’t just depend on the action; it depends on the resulting state transition (S, a, s’). Therefore, we need a more powerful way to measure value.
We define the Return as the total weighted sum of future rewards.
The Discount Rate (in [0, 1)) is a hyperparameter that determines the importance of future rewards compared to immediate rewards.
The State Value Function is the expected return (G_t) starting from state $s$ while following a specific policy pi:
This function is critical because it allows us to compare policies. An optimal policy pi* is one that maximizes $v_{\pi}(s)$ for all states s in S. The Deterministic Optimal Policy Theorem states that for any finite MDP, at least one deterministic optimal stationary policy pi* exists.
The Bellman Equation is derived from the MDP and is valid for all MDP problems. It is important because it shows the recursive definition of the value function.
The magic of the Bellman Equation lies in rewriting the infinite sum of the Return G_t into a simple recursive expression:
Applying the expected value based on the policy pi and the transition T, the State Value Function $v_{\pi}(s)$ can be expressed as:
In simple terms, the value of the current state ($v_{\pi}(s)$) is the expected value of the immediate reward plus the discounted value of the next state ($v_{\pi}(s’)$). This allows us to deal with the value function without an infinite number of terms.
The Action Value Function ($q_{\pi}(s, a)$) measures the expected return when starting in state $s$, taking action $a$, and then following policy $\pi$.
It is also defined recursively and is related to $v_{\pi}(s)$:
The most important insight is the Optimal Bellman Equation, which defines the conditions that the optimal value function ($v_*$ or $q_*$) must satisfy.
The optimal policy ($\pi^*$) always chooses the action with the highest value.
2. Optimal Action Value: The optimal value of state-action pair $(s, a)$ is the expected immediate reward plus the discounted maximum optimal action value in the next state $s’$38:
The optimal policy ($\mu^*$) is then simply the action that maximizes this optimal action value:
The Bellman Optimality Equation serves as a critical target function condition for solving RL problems41. Any policy, value function, or action-value function that models an MDP must obey the Bellman Equation.
<hr><p>The Foundation of Reinforcement Learning: MDPs and the Bellman Equation 🧠 was originally published in KAIST Include AI Club on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>