Imagine for a second, you know, that you're making
a highly complex decision. Right. But the catch
is the outcome of every single choice you make
is just slightly unpredictable. Which is, I mean,
pretty much all of life, right? Exactly. Think
about navigating your career over the next decade
or If you want to get a bit more technical, imagine
trying to manage the routing of millions of data
packets in a global telecom network. Yeah, you
can make a choice. You can take an action, but
you can never be. 100 % certain of what the exact
result will be. Because the environment always
pushes back. Exactly. No matter how precise your
intentions are, there's always this inherent
element of randomness or, you know, noise between
your action and the final outcome. So navigating
life or even designing an artificial intelligence
to do it for us is essentially like playing a
board game where the dice are slightly loaded.
Yeah. And the rules occasionally shift while
you're looking the other way. So how do we actually
map that out mathematically? Today we are going
on a deep dive into the Markov decision process,
or MDP for short. Yeah, it's such an elegant
concept. It remains the foundational mathematical
framework for sequential decision making under
uncertainty. And we are pulling from a really
comprehensive Wikipedia article on the subject
for this deep dive. We are. The framework was
originally formalized back in the 1950s within
the field of operations research, and it borrows
its name from the Russian mathematician Andrei
Markov, specifically relying on the Markov property.
Right, the Markov property, which is this assumption
that the future depends only on your present
state. It completely ignores the sequence of
events that preceded it. Your current situation
is literally all that matters for the next step.
You don't need to consult a history book to calculate
your next best move. Exactly. The past is irrelevant
to the math. So our mission today is to give
you, the listener, a shortcut to being deeply
informed on how this actually works under the
hood. We want to take these incredibly dense
concepts like value iteration, Q -learning, and
continuous time differential equations and just
translate them into a relatable framework. A
framework that really explains how systems, and
frankly humans, learn to survive in totally unpredictable
environments. Okay, let's unpack this. Since
we're talking to an audience that already knows
their way around basic modeling, we can fly through
the standard blueprint pretty quickly. Right,
the classic four -tuple. Yeah, the four -tuple.
States... Actions, probabilities, and rewards.
S, A, P, and R. Which is basically the board,
the pieces, and the rules. Right. S is where
you are. A is your menu of available moves. And
R is the immediate payoff. But the tricky variable
here is P, right? The probability transition.
Yeah, P is where things get messy. Because how
does the math actually handle the likelihood
of landing in a specific future state? Well,
what's fascinating here is how the mathematics
of that probability transition, that p variable,
has to warp depending on the nature of your environment.
Warp how? So if your state space is discrete
-like, think of the finite squares on a chessboard.
The probability is calculated using a simple
counting measure. You're essentially just adding
up distinct separate outcomes to find your odds.
It's very clean. But what if it's not a chessboard?
What if it's fluid? Right. If your states are
continuous, Say you're tracking the precise temperature
of a server rack down to the decimal, the math
shifts, you have to use the Lebesgue measure.
Lebesgue measure. Yeah. Instead of counting individual
drops of water, you're integrating over a continuous
area to calculate the volume of a fluid. The
probability becomes a curve that you actually
have to find the area under. OK. Let's ground
this in a classic example from control theory
to make it real. The pole balancing model. Oh,
classic. Imagine you're trying to balance a long
broom on the palm of your hand. The state, S,
is made up of continuous measurements, right?
Yeah, the position of your hand, the speed it's
moving, the angle of the broom, the angular velocity
of its fall. Exactly. And the action, A, is applying
force to the left or the right. And your reward,
R, is simply a one if the broom stays up and
a zero if it drops. Right. But wait, I want to
challenge something here. Before it. If pole
balancing is driven by the strict deterministic
laws of classical mechanics, why do we need that
P variable at all? Isn't physics entirely predictable?
Theoretically, yes. Gravity and momentum follow
very strict equations. Right. But in practice,
physical execution is messy. Think about it.
If we're talking about a robotic cart trying
to balance that pole, the sensors reading the
angle might have a millisecond of latency. Oh,
sure. or the motor might experience a tiny microscopic
voltage drop, causing it to push slightly weaker
than the math commanded it to. I see. The MDP
framework uses that probability transition, P,
to mathematically absorb the noise of reality.
You might command the court to move exactly two
inches to the right, but P dictates the bell
curve of where it actually ends up. OK, that
makes total sense. Yeah. So the four -tuple gives
us the board, the pieces, and the physics engine
of our game. But to actually win, We need an
objective. We need a strategy. Right. Which the
framework calls a policy, denoted by the Greek
letter pi. Yeah, a policy is simply a mapping
function. Think of it as a massive lookup table
telling the agent exactly which action to take
for every single conceivable state. And the goal
is to find the optimal policy, the one that maximizes
the sum of all future rewards. Exactly. But here's
the thing. If you're looking at a potentially
infinite horizon of future decisions, you can't
just treat a reward 10 years from now. the same
as a reward today. You really can't. Which brings
us to the discount factor, gamma. Gamma, a number
between zero and one. Yes. Is setting gamma below
one essentially like reverse compound interest
or like financial inflation? How do you mean?
Like deciding between eating one marshmallow
right now versus two marshmallows in an hour.
A dollar today has more purchasing power than
a dollar in a decade. So we mathematically force
the AI to care about the near term. That is a
highly accurate way to look at it. It acts as
an inflation rate on the value of success. If
gamma is low, say 0 .1, the inflation is brutal.
The algorithm only cares about the immediate
payoff because future rewards are deemed worthless.
But if gamma is 0 .99, it's willing to invest
in long -term strategies. But why not just set
gamma to exactly one? Wouldn't we just value
all future rewards equally? Why do we specifically
need to be short -sighted? because of the math
of infinity. If an algorithm runs forever and
it values all future rewards equally, the total
expected reward adds up to infinity. You can't
mathematically compare two strategies if they
both just yield an infinite score. Right. Infinity
equals infinity. Exactly. By enforcing a discount
factor, the value of those distant future rewards
eventually decays to zero, which allows the total
sum to converge on a finite number. It literally
forces the math to be solvable. It does, though
I should mention there are alternatives. In learning
theory, researchers sometimes use what's called
the H -step return. The H -step return? Yeah.
Instead of an inflation rate slowly fading the
future out, the H -step return enforces a hard,
strict deadline. Like a cutoff. Exactly. It tells
the agent to maximize the reward over the next
eight steps, weighting them all equally, and
ignoring absolutely everything that happens after
that deadline. Wow. And there is a reassuring
mathematical guarantee built into this framework
too, right? Oh, regarding deterministic policies.
Yeah. If your environment is entirely deterministic,
meaning taking action x and state y will yield
the exact same reward 100 % of the time, there
will always be an optimal policy that is also
purely deterministic. Yes. The agent will never
need to randomly roll the dice on its actions
to succeed. But, you know, knowing an optimal
policy exists mathematically is very different
from a computer actually calculating it. Oh,
totally different. If an AI is playing out millions
of futures, where is it storing all that data
to compare it? So, to solve finite MDPs, computers
rely on dynamic programming. which requires allocating
memory for two massive data structures. Arrays,
right. Yeah. A value array which estimates the
expected long -term reward for being in a specific
state. and a policy array, which stores the best
known action for that state. And how do we actually
fill those arrays? Well, the first foundational
method is value iteration, formulated by Richard
Bellman back in 1957. It uses backward induction.
And the crazy thing is, the algorithm doesn't
even attempt to store a specific policy at first.
It literally populates the value array with completely
random guesses. Wait. Just garbage random numbers.
Total garbage. Then, it sweeps through the entire
state space, looking at the neighboring states,
and recursively updates its guesses based on
the highest possible expected returns of those
neighbors. But wait, if it starts with garbage
random guesses, how does recursively updating
garbage eventually lead to the perfect mathematical
truth? It works because of the Banach Fixpoint
Theorem. The Banach Fixpoint Theorem. Yes. As
long as your discount factor, your gamma, is
strictly less than one, the theorem proves that
the mathematical distance between the algorithm's
current guess and the true optimal value inevitably
shrinks with every single sweep. So the errors
just get compressed out. Exactly. It iterates
until the numbers converge and stop changing
entirely. That's incredible. And then we have
the second major method, right? Policy iteration.
Introduced by Ronald Howard in 1960. Yeah. And
instead of just guessing values, policy iteration
constantly alternates between two distinct steps.
Right. It evaluates and improves. First, it locks
in its current policy and calculates exactly
how much long -term reward that specific strategy
will yield. Okay. Once it knows the value of
its current behavior, it scans the states to
see if flipping a single action would increase
that value. And if it does? If it finds a better
action, it updates the policy array and then
starts the evaluation phase all over again. The
history behind this is amazing to me. Ronald
Howard didn't invent policy iteration for some
high -tech robotics lab. No, he did it. He invented
it to solve a massive logistical nightmare for
this year's catalog. It's such a great story.
He needed to figure out exactly who should get
a physical catalog mailed to them to maximize
profits. And to map that to our four -tuple,
Howard treated the customer's purchasing history
over the last six months as the state. Right.
The action was a simple binary choice. Spend
the 50 cents to mail a catalog or don't. And
the probability. The transition probability was
the statistical likelihood that sending the catalog
would prompt the customer to buy a $10 item,
transitioning them into a new state of purchasing
frequency. That is wild. Yeah. By bouncing back
and forth between evaluating the mailing strategy
and improving it, he found the exact mathematical
threshold where the cost of mailing broke even
with the expected future revenue. But here is
where I think the pure math hits a brick wall.
OK, lay it on me. This dynamic programming operates
in polynomial time, which is generally efficient,
but it suffers from the curse of dimensionality.
The curse. Because if I add just a few more variables
to my state space, say we are routing those telecom
packets we mentioned earlier, and we add latency,
packet size, and server temperature to the mix.
The number of possible states just explodes exponentially.
Exactly. The arrays become too massive for any
computer RAM to hold. Yeah. So how is this framework
actually useful in modern, complex applications
if the state space basically breaks the hardware
immediately? Well, if we connect this to the
bigger picture, you are highlighting exactly
why engineers rarely use pure exhaustive dynamic
programming today. We don't. No, we used targeted
approximations. Techniques like prioritized sweeping.
prioritized sweeping. Yeah, instead of updating
the value of every single state in the array
equally, the algorithm calculates a mathematical
error margin for each state. It preferentially
spends its computational energy updating the
states with the largest errors. The states where
the action is actually happening. Exactly. Ignoring
the millions of corner cases that will likely
never occur. Or we use Monte Carlo tree search,
right? which simply samples a few likely paths
into the future rather than exhaustively calculating
every single permutation of the universe. Spot
on. But, you know, value iteration and policy
iterations still fundamentally require you to
know the rules of the game upfront. You need
the transition probabilities. Right. The p variable.
Yeah. What happens if you are a robotic agent
dropped into an environment with zero instructions,
totally blind to the physics of the world? That
requires abandoning pure dynamic programming.
and moving to simulators and reinforcement learning.
Exactly. If you don't have the probability matrix,
you have to interact with the environment to
reverse engineer it. So you use a simulator.
You can use an episodic simulator, which drops
you into a state and lets you take actions until
you hit a failure or a success, generating a
full trajectory of experience. OK. So that's
like playing a level of a video game from start
to finish, just learning the physics engine by
trial and error. Exactly. Or you use a generative
model, often written as G of S comma A. Right.
This is a single step simulator. You hand it
any state and any action, and it instantly generates
the subsequent state and reward for you. Oh,
wow. Yeah. It allows the algorithm to sample
the environment's reactions without having to
linearly play through the entire timeline just
to reach that specific scenario. So this brings
us to reinforcement learning, or RL. But I'm
stuck on one thing here. If the agent doesn't
know the probability map, How on earth is it
learning a mathematical policy just by taking
actions? I mean, isn't button mashing just chaos?
It can be. Here's where it gets really interesting.
How does a random success turn into a formalized
strategy? It relies on sample efficiency and
a massive breakthrough algorithm called Q -learning.
Q -learning? Yeah. Instead of trying to reconstruct
that massive probability matrix of how the world
works, Q -learning bypasses the physics entirely.
It just ignores the rules. Pretty much. It builds
a Q -table where the Q stands for the quality
of a specific state action pair. But mechanically,
How does the math update when it actually finds
a reward? Through what's called a temporal difference
update. Okay, walk me through that. Let's say
the agent takes an action and unexpectedly hits
a massive reward. It doesn't just record that
the current state is good. The algorithm takes
a fraction of that reward and mathematically
pushes it backward to the Q value of the state
action pair that immediately preceded it. Like
leaving a breadcrumb trail. Exactly like a mathematical
breadcrumb trail. Over thousands of episodes,
the rewards propagate backward through the queue
table, lighting up the best sequence of actions
without the agent ever needing to calculate the
underlying probability of the environment. It's
learning entirely by consequence. Pure consequence.
But even with queue learning, we are assuming
the agent knows exactly what state it's currently
in. What if the sensors are broken? Or what if
you're playing poker and the opponent's cards
are hidden? That introduces the first major extension
of the framework, partial observability or POMDP.
The POMDP. Yeah. When an agent cannot directly
observe its true state, it has to maintain a
probability distribution over all the possible
states it might be in. This is called a belief
state. A belief state, okay. Every time it takes
an action and receives an observation, it uses
Bayes' theorem to update its belief state, and
then it makes its next decision based on that
distribution of probabilities rather than a concrete
fact. Man, the math must get heavy. And what
about constrained MDPs or CMDPs? In the real
world, you are rarely just trying to maximize
one single reward. CMDPs are heavily utilized
in robotics and autonomous driving, actually.
Really? Yeah. Think about it. You want an autonomous
car to reach its destination as fast as possible,
but you have rigid constraints. It cannot exceed
the speed limit, and it absolutely cannot hit
a pedestrian. Right, obviously. The math here
fundamentally changes. You can't solve it with
standard dynamic programming anymore. You have
to use linear programming to balance the multiple
competing cost functions. Wow. And fascinatingly,
the optimal policy in a constrained environment
actually changes depending on what state you
start in. Because your starting battery life
or starting position restricts the mathematical
envelope of what moves are safely available to
you. Exactly. But I think the most mind -bending
extension we need to cover is the continuous
time Markov process. Oh yeah. In a board game
or even a digital simulator, time ticks in discrete
turns, right? Step one, step two. Yeah, but during
something like a viral epidemic or a continuous
flow of data packets in a telecom queue, time
is constantly flowing. How do you mathematically
map a decision space when actions can happen
at literally any millisecond? This raises an
important question about how we actually digitize
reality. In a standard MDP, time is a staircase,
and you sum up discrete rewards over distinct
steps. But in continuous time, the system dynamics
are governed by ordinary differential equations,
ODE's. So time becomes a smooth ramp. Exactly.
The mathematics replace discrete summations with
continuous integrals. You are calculating the
shifting area under a curve. But if you aren't
waiting for a discrete clock to tick, How do
you calculate the optimal move? You use the Hamilton
-Jacobi -Bellman equation or the HJB equation.
Okay, the HJB. Instead of looking ahead to step
t plus 1, the HJB equation takes the limit as
the change in time approaches zero. It uses partial
derivatives to find the continuous rate of change.
So it's constantly updating. Yes, it provides
an optimal control vector that continuously steers
the system based on instantaneous feedback rather
than waiting for a turn to end. Like you're actively
steering a ship through flowing water, constantly
adjusting the rudder rather than moving a static
piece on a grid. That's a great analogy. Okay,
let's bring this all together. We started with
the rigid four -tuple states, actions, probabilities,
and rewards. We looked at the math of balancing
a pole, we saw how Ronald Howard conquered the
Sears catalog mailing list, and we move through
the Wild West of key learning and continuous
time differential equations. So what does this
all mean for you, the listener? To put it simply,
the theoretical mathematics of artificial intelligence
really mirror the algorithms you run in your
own head. Every single day, you are operating
as an agent in a partially observable environment.
You truly are. Every time you choose a new route
to work or try a new communication style in a
meeting, you are taking an action under deep
uncertainty. You are updating your personal internal
Q values based on the unexpected rewards or penalties
you encounter. You are leaving yourself a breadcrumb
trail of what works and what doesn't, slowly
refining your optimal policy for life. And your
personal discount factor, your gamma, dictates
whether you are trading your future potential
for an immediate payout or investing in actions
that might not yield a reward for a decade. I
love that. And I want to leave you with one final
provocative thought. There is a deeply abstract
mathematical field called category theory. And
when applied to MDPs, it creates a context -dependent
Markov decision process. Right. In this interpretation,
moving from one context to another doesn't just
change your state. It fundamentally alters the
entire set of available actions and the laws
of probability governing them. Meaning, the rules
of the game, the very physics of your choices
change entirely depending on the mathematical
object or environment you place yourself in.
I want you to ponder that in your own life. Think
about that board game with the loaded dice we
talked about at the very beginning. How does
simply changing your context, moving to a new
city, switching careers, or even just changing
who you surround yourself with, completely rewrite
your mathematical landscape for future possibilities?
Most of the time, we are so focused on calculating
the best move within our current game, we forget
that we have the power to change the board entirely.