Reinforcement Learning

TL;DR: Fundamentals of RL followed by an introduction into model-based vs model-free methods, policy-based methods, value-function methods, dataset collection (online, offline) distinctions, and practical implementation tips.

Motivation

Why now?

AI chat technologies powered by LLMs are changing the world (Anthropic, OpenAI, Deepseek). The goal of this series is to help you see in Figure 1 and understand it and the underlying intuition.

Series Outline

In this RL series we’ll start with the fundamentals of RL and work up from that, building upon intuitions and concepts to help reinforce (haha) your understanding.

1. Setup (← this blog)

2. Coming soon

By the end of this blog, you should be able to answer the following questions

1. What is Reinforcement Learning? What “problem” is it learning?

2. How do we define the environment? How do we define a state? How do we define an action? How do we define a reward?

3. What is a Markov Decision Process (MDP)?

Setup

For me, reinforcement learning is best modeled by human babies. Imagine a baby crawling around and trying to eat an object where if the object is food and is yummy the baby eats it otherwise the baby spits it out. As this baby crawls around exploring sometimes it eats or spits out something changing the world (the object is consumed or has saliva all over it). Through this the baby learns what's good and what’s gross!

Notice that data in Figure 3 represents a trajectory.

$$\tau := ((s_0, a_0, r_0), ..., (s_T, a_T, r_T))$$

Reinforcement Learning (RL) is interested in being able to learn from a trajectory of behaviors, or a sequence of actions and resulting world states, as we interact with the environment. The core idea is that the environment responds to our actions and we iteratively act in this environment. It’s an interaction between an agent & the environment. Another way to phrase RL is a learning algorithm for agents trying to understand how to behave in an environment with unknown state transitions.

Markov Decision Process?

Personally, working through an example has always been more useful to me than just talking through it. Let’s take a driving video as an example.

What is state? A state is a representation of the world and the agent. In RL, the state contains all the information needed to achieve our goal (which in this case means maximizing our reward). In our driving scenario above, our reward could just be driving well and getting to our destination. If that’s the case, our state could be where our car is, its orientation (the car pose) and the car’s current velocity. What’s our action then? It should be whatever controls the cars movement through space such as steering angle and acceleration.

Congrats! According to RL we’ve perfectly captured the state of the world, right? Or have we? What are some problems with this formulation? Well for one we didn’t include the pose (a person’s location and orientation in space) of the person who crossed the street! So let’s add that to our state.

But what if there’s another person? What if a tree has a nonzero chance of falling in front of us? What if a meteor fell and hit our car?

So you see the problem with any state formulation is that it’s not able to fully capture the entire world even though we want it to. Maybe if our state vector tracked every atom’s pose in the universe as well as all combinations of every possible chemical interaction between all atoms we’d be able to fully capture the environment but that’s not really possible at the moment*.

For the most part, state is a “good-enough” encapsulation of the entire world for our particular problem. For instance, maybe we really only care about our vehicle’s safety and not the surrounding agents so our reward is only “drive well and don’t hurt the vehicle”. Then we can restrict our car’s “world” to a 100mx100m view around the vehicle which is much smaller than the whole universe! You can see how formulating the modeling of the problem by defining rewards and modeling the world before even optimizing an RL objective is a challenge!

But effectively this is what most RL in the literature assumes, it describes a state (or a learned state which we’ll discuss later) as an observation of the world like a camera images, smells, sounds, etc. Some methods model the transition between states and others do not; called model-based and model-free RL respectively which we’ll discuss in future blogs.

Observation vs State

An observation is a partial view of the state, ie we’ve only observed a part of the whole world. This is like looking at our universe state (the vector containing all the atom poses) seeing only a fraction of it and encoding it in some way. An example is a single camera image.

Ok let’s pretend we let camera images be our state. In figure 4 we correctly slam on the breaks (high reward) but in figure 5 we’d penalize the model because it’s green and we’re stopped!

If we had a penalty for not going on a green light, then we’d be unfairly penalized because the minute the person left the frame we no longer are rewarded for having no collision!

This illustrates a fundamental property of observations and states: observations are highly dependent through time but states are not!

Cue the Markov Decision Process (MDP).

$$\begin{aligned} \mathcal{M} &= \bigl(\mathcal{S}, \mathcal{A}, P, R, \gamma\bigr),\\[6pt] \text{where:}\\ &\mathcal{S}\text{ is a set of states,}\\ &\mathcal{A}\text{ is a set of actions,}\\ &P_{env}(s' \mid s,a)\text{ is the transition probability function, giving the probability of}\\ &\quad\text{moving from state }s\text{ to state }s'\text{ under action }a,\\ &r(s, a)\text{ is the reward function, giving the immediate reward for taking}\\ &\quad\text{action }a\text{ in state }s,\\ &\gamma \in [0,1]\text{ is the discount factor, which discounts future rewards}\\ &\quad\text{relative to immediate rewards.} \end{aligned}$$

Formally an MDP is a tuple of states, actions, transitions to different states via state action pairs, associated rewards, and a discount factor. An MDP is called Markov because the underlying structure of state transitions follows the markov property which mathematically is expressed as

$$Pr[s_{t+1} | (s_t, a_t), (s_{t-1}, a_{t-1}), ..., (s_{0}, s_{1})] = Pr[s_{t+1} | (s_t, a_t)]$$

This translates roughly to: knowing the present tells you about the future independent of the past. Keep in mind, most things aren’t Markovian.

Markovian examples:

• Radioactive decay: the probability of whether or not an atom has decayed or not only depends on whether it has or hasn’t decayed.

• Populations: Simple population models like the birth and death process can be modeled as Markovian where birth rates and death rates only depend on the current population not the past population size.

• Classical mechanics.

Non Markovian examples:

• Video: A person dectector per frame: A person walks behind a car and suddenly emerges a few frames later. This is not markovian because knowing a person was behind the car can help you predict if a person exists

• Springs: Predicting the force of the spring. This depends on how many times it was used and how it was used as strong forces can hurt the material. Thus this depends on previous examples.

So even though observations may look like state make sure to recall that state in an MDP sense needs to satisfy the Markov property on the state transitions of the environment.

There’s also something called Partially Observable MDPs (POMDP) but that’s a discussion for another time.

Notion & Definitions

Now that we can more adequately state what RL is trying to do.

Fundamentally, RL tries to optimize the following equation where theta represents the parameters of an agent policy.

$$\begin{aligned} \begin{gather} \displaystyle \max_{\theta} E_{\tau \sim p_\theta} [\sum_{t}^T r(s_t, a_t)] \\ s.t.\ \ p_\theta := p_\theta(s_0)\prod_{t}^Tp_{env}(s_t | s_t, a_t)\pi_\theta(a_t | s_t) \end{gather} \end{aligned}$$

Where we have some trajectories , unknown transition parameters from the environment, r(s_t, a_t) is the reward for a specific state and action, and some parameters representing our agent theta in a markov decision process. We’ll go through each of these concepts.

The “Black Box” of RL

• The black box of RL typically alludes to not knowing the state-transition probabilities and being unable to effect them.

Next time

• We’ll discuss the difference between model-based and model-free approaches, present MPC vs REINFORCE, walk through some of the basic setup and mathematical intuition.

Appendix

*Note that’s a vector of dimension C * 2 ^ (10 ^ 23) - 1 scalers for just C chemical interactions.