Introduction to Reinforcement Learning

Reinforcement learning is basically the closest learning paradigm we have to how humans and animals actually learn. Instead of feeding a model labeled datasets, we put an agent in an environment and let it figure things out through trial and error. By interacting with its surroundings, the agent learns to make decisions that maximize some notion of cumulative reward over time.

At any time $$t$$ :

We have an agent in an environment (like a baby in a room).
The agent observes the environment and chooses an action.
The environment changes and the agent receives feedback.

The key components are:

State: The current situation/description of an environment.
Rewards: This is what the agent works for; for any action it does, it receives a reward. RL works by rewarding an agent present in an environment for an action it committed until it reaches the final state/desired goal.
Actions: Actions are the choices available to an agent, the things it can do to the environment.
Policy: It defines the behavior of an agent and how it acts on the environment. Based on the existing states of the environment, it talks about what actions to take.
Value Function: It is a function that evaluates long term benefits and ensures that the long term goal is being reached.
Model: It mimics the environment and its behavior and allows us to predict what can happen in it. For a given state and action, we can predict the next state and reward.

State

A state is a complete description of the environment at any time.

A state $$s$$ at any time $$t$$ : $s_t \in S$ Taking the example of a chess board, a state of the environment (the chess board) is the position of all pieces at any given time $$t$$ .

It is the description of the environment given to the agent on the basis of which it takes an action.

Markov Property

For a process to be considered a Markov Decision Process, the state must satisfy the requirement:

The future state depends only on the present state, not the entire past history.

In a game of chess, the current board tells you everything you need to know to make your best move; you don't need to know your previous moves to understand what to do.

Future ⊥ Past | Present

This means that the future is independent of the past, only depending on the present.

P(s_{t+1} \mid s_t, a_t) = P(s_{t+1} \mid s_0,a_0,\dots,s_t,a_t)

This means that the probability of the state

s_{t+1}

given the current state

s_{t}

and action

$a_t$

is equal to the probability of moving to the next state given the entire history of states and actions

s_0,a_0,\dots,s_t,a_t

If a system's future depends on something that happened five steps ago, then that system is non Markovian.

This is done so that the problem is solvable; without this, the complexity of the problem becomes infinite.

It is computationally efficient for a system to satisfy the Markov property.

Actions

An action is a choice available to the agent; it is the list of options it can perform in the environment at the current state.

a_t \in A(s_t)

Action at time step

$t$

chosen from the set of actions

$A(s_t)$

available in state

$s_t$

Actions depend on state and actions affect the future.

In chess, actions are all the legal moves possible.

Action space is the set of all possible actions in an environment.

Transition Dynamics

Transition dynamics talk about how the state and environment change when the agent takes an action.

It is represented as:

P(s_{t+1} \mid s_t, a_t)

This tells us the probability of transitioning to state

s_{t+1}

from state

$s_t$

when taking action

$a_t$

Reward

This is the feedback we give to the agent.

An action is either good or bad, and hence rewards are given on the basis of whether what the agent did ultimately reaches the end goal or not.

Reward is defined as:

r_{t+1} = R(s_t, a_t, s_{t+1})

For transitioning from state

$s_t$

to state

s_{t+1}

after taking action

$a_t$

Policy

It defines the behavior of the agent. It tells the agent what actions it should take for a given state.

For example:

If a player is at a state where they can take a pawn, their policy at that state should be to choose the action to take the pawn.

Policy is a mapping; it takes a state as input and outputs an action.

Policy is defined as:

\pi(a \mid s) = P(a_t = a \mid s_t = s)

$\pi$ is the standard symbol for policy.

So, policy gives us the probability of taking action $$a$$ given state $$s$$ , $P(a \mid s)$ .

In the beginning, the agent doesn't know what actions are best. Its policy tells it to try different things, but as it gets rewards, it updates the probabilities $\pi$ .

Hence, the overall goal of RL is to find the optimal policy, which tells the agent the best actions to take to maximize the cumulative reward.

Return

Return is denoted as $$G_t$$ ; it is the sum of rewards the agent receives from time step $$t$$ until the end of the episode:

G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots

\gamma

is a discount factor (between 0 and 1). So, the discount factor scales down the impact of future rewards compared to immediate ones.

As you can see, we use higher powers of the discount factor as we go further into the future because:

We want the agent to understand that a reward now is better than a reward later.
In continuing tasks, summing up rewards to get a return might give us an infinite return, so we do this to ensure that the return is a finite number.

True Objective

The true objective of the agent is to maximize the expected return, which is the sum of all discounted rewards it will receive.

\max_\pi \mathbb{E}_\pi [G_0]

Value Function

It is the expected cumulative reward (the return) an agent can achieve starting from a given state or state action pair. It serves as a guide to evaluate the long term performance of the agent and to see if it is heading towards the goal of maximizing rewards.

It is a representation of the future.

There are two types of value functions:

State Value function: It estimates the expected return starting from a state. It tells us, for the current state and policy, what the expected reward is. $V^\pi(s) = \mathbb{E}_\pi [G_t \mid s_t = s]$

Action Value function: It estimates the expected return from taking a specific action in a state and then following the policy. This tells us how good a particular action is in a given state.

Q^\pi(s,a) = \mathbb{E}_\pi [G_t \mid s_t=s, a_t=a]

Bellman Equation

It is a formula used in reinforcement learning to calculate the value of a state as the immediate reward plus the discounted value of future states.

The value of a state is equal to the reward received now plus the expected value of the next state.

This helps agents make better decisions by considering both immediate and future rewards.

We start from the recursive definition of return:

G_t = r_{t+1} + \gamma G_{t+1}

We take the expectation conditioned on state

$s$

V^\pi(s) = \mathbb{E}_\pi[r_{t+1} + \gamma G_{t+1} \mid s_t = s]

This expectation is split:

V^\pi(s) = \mathbb{E}_\pi[r_{t+1} \mid s_t=s] + \gamma \mathbb{E}_\pi[G_{t+1} \mid s_t=s]

It is split based on the current reward and the future return.

We expand these expectations over actions and transitions. Actions are chosen by the policy, and the next state is determined by the environment's transition dynamics.

V^\pi(s) = \sum_a \pi(a\mid s) \sum_{s'} P(s'\mid s,a) \Big[ R(s,a,s') + \gamma V^\pi(s') \Big]

So, the value is equal to the sum over all possible actions of the policy probability, times the sum over all possible next states of the transition probability, multiplied by the outcome value (the immediate reward plus the discounted value of the next state).

The policy part gives us the probability of taking each action under the policy.

The transition part describes the probability of transitioning to other states given the chosen action.

The outcome value is the sum of the immediate reward and the discounted estimated value of the next state.

We multiply these components because the joint probability of choosing action $$a$$ and transitioning to state $$s'$$ is the product of their individual probabilities (using the chain rule of conditional probability): $P(a, s' \mid s) = \pi(a \mid s) P(s' \mid s, a)$ .

Quality

Quality is the long term value of a state action pair. It tells us if the action is actually good in the long run.

$Q^\pi(s,a)$ is the expected return starting from state $$s$$ , taking action $$a$$ , and then following policy $\pi$ forever after.

Q^\pi(s,a) = \mathbb{E}_\pi [ r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots \mid s_t = s, a_t = a ]

In a game of chess, the Q value of a move is how that move will affect us in the long run. For example, a move that traps the opponent's Queen will have a huge Q value.

So, Q is basically the expectation of return:

Q^\pi(s,a) = \mathbb{E}_\pi [ G_t \mid s_t = s, a_t = a ]

Tasks

Episodic Tasks

An episodic task has a terminal state and is broken into episodes. Examples include chess, Go, Atari games, etc.

Formally, an episode ends at a time step $$T$$ .

Return is:

G_t = \sum_{k=t+1}^{T} \gamma^{k-t-1} r_k

The terminal state has a value of:

$$V(s_T) = 0$$

Continuing Tasks

Continuing tasks have no terminal state, and the interaction goes on forever. Examples include stock trading agents, recommendation systems, etc.

We need a discount factor to make the return finite: $\gamma < 1$

Deterministic Tasks

In deterministic tasks, taking a specific action in a state leads to an exact next state. For instance, if you make a move in chess, it leads to one specific board state.

P(s' \mid s,a) \in \{0,1\}

Stochastic Tasks

In stochastic tasks, an action can have multiple outcomes. Examples include robotics, real world systems, etc.

P(s' \mid s,a) \text{ is a probability distribution}

Exploitation vs Exploration

It refers to the trade off between exploitation and exploration.

Exploitation is choosing and continuing the action that you currently believe is best:

a = \arg\max_a Q(s,a)

The problem is that our current estimates might be wrong, meaning we might miss out on a better action.

Exploration is trying out different actions to gain more information. By exploring, the agent learns which actions yield higher rewards and which do not.

This trade off is important because we want an agent that balances exploration and exploitation to maximize long term rewards.

Two Approaches to RL

There are two main approaches to reinforcement learning: value based and policy based.

Value Based Methods

In value based methods, we learn how good a state is, or how good a specific action is in a given state.

V^\pi(s) = \mathbb{E}_\pi [ G_t \mid s_t = s ]

This is the value of the current state (its expected return).

Q^\pi(s,a) = \mathbb{E}_\pi [ G_t \mid s_t = s, a_t = a ]

This tells us how good an action is for a particular state. It is the expected return when an action is applied in a state.

Q^*(s,a) = \max_\pi Q^\pi(s,a)

This is the optimal action value function, representing the best expected return we can get from any policy. We extract the policy greedily based on the optimal action values:

\pi(s) = \arg\max_a Q^*(s,a)

This means we choose the action that has the highest optimal value.

Common algorithms include:

Tabular Q learning
SARSA
Deep Q Networks
Double DQN and Dueling DQN

In value based methods, we do not parameterize the policy directly. Instead, we focus on learning the best value (cumulative reward) for actions, and the policy is implicitly defined by choosing the best action.

Policy Based Methods

In policy based methods, we learn the policy directly instead of relying solely on action values. $\pi_\theta(a \mid s)$ Here, $\pi_\theta$ represents a policy parameterized by $\theta$ (the weights of a neural network) that outputs the probability of taking action $$a$$ in state $$s$$ . The objective is to maximize: $J(\theta) = \mathbb{E}_{\pi_\theta} [ G_0 ]$ It is like learning an overall strategy instead of just looking at the next best move.

We adjust the weight vector of the neural network ( $\theta$ ) to maximize the expected return $J(\theta)$ .

To do this, we use Gradient Ascent, calculating the gradient of the objective function with respect to the weights to update them in the direction that increases the reward.

This allows for a stochastic policy rather than the deterministic greedy policy used in value based RL.

The policy gradient theorem gives us the gradient of the objective:

\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} \big[ \nabla_\theta \log \pi_\theta(a \mid s) Q^\pi(s,a) \big]

Ultimately, policy gradient methods directly optimize the agent's strategy by adjusting policy parameters, making them super powerful for handling complex action spaces. Choosing between value based and policy based methods—or combining them in actor critic architectures—is one of the core design decisions in modern RL. Next, we will see how these foundations lead to practical deep reinforcement learning algorithms.