Overview of Reinforcement Learning

Basic Terminologies in Reinforcement Learning(RL)

Reinforcement Learning is defined by the following components:

• Agent: The entity that interacts with the environment and makes decisions.

• Environment: The world in which the agent operates. Mathematically defined as a state transition system: $\mathcal{E}: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{S}$

• State ($s \in \mathcal{S}$): The current configuration of the environment.

  • The state space $\mathcal{S}$ is the set of all possible states.
  • At time step $t$, the state is denoted as $s_t$.

• Action ($a \in \mathcal{A}$): The decision made/ action taken by the agent after observing the state $s_t$ of the environment based on its policy $\pi$.

  • The action space $\mathcal{A}$ is the set of all possible actions.
  • At time step $t$, the action is denoted as $a_t$.

• Reward ($r \in \mathbb{R}$): The feedback signal received by the agent from the environment after taking an action.

  • Mathematically defined as: $r: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ is a real-valued function that maps the current state, action, and next state to a scalar reward.
  • At time step $t$, the reward is denoted as $r_t = r(s_t, a_t, s_{t+1})$, which represents the reward received at time step $t$.
  • Note that in some books the reward function is defined as $r_{t+1} = r(s_t, a_t, s_{t+1})$, which represents the reward received at time step $t+1$. However I like to use the earlier definition to avoid confusion.

• Policy ($\pi$): The strategy that the agent follows to select actions.

  • Deterministic policy: $\pi: \mathcal{S} \rightarrow \mathcal{A}$
  • Stochastic policy: $\pi: \mathcal{S} \times \mathcal{A} \rightarrow [0,1]$, where $\pi(a|s)$ is the probability of taking action $a$ in state $s$.

• State Transition Probability ($p$): The probability of transitioning to state $s’$ after taking action $a$ in state $s$.

  • Mathematically: $p(s’|s,a) = \mathbb{P}(s_{t+1}=s’|s_t=s, a_t=a)$
  • This defines the dynamics of the environment and captures how actions influence state changes.
  • For deterministic environments: $p(s’|s,a) = 1$ for exactly one next state $s’$ and 0 for all others.
  • For stochastic environments: $\sum_{s’ \in \mathcal{S}} p(s’|s,a) = 1$ for all state-action pairs $(s,a)$.

• Episode: A sequence of state-action-reward transitions from an initial state to a terminal state.

  • Mathematically: $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, …, s_T, a_T, r_T)$
  • $T$ is the time step when the terminal state $s_T$ is reached.

• Trajectory: A sequence of states, actions, and rewards generated by following a policy $\pi$ from an initial state $s_0$.

  • Mathematically: $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, …, s_T, a_T, r_T)$
  • A trajectory represents the complete history of an agent’s interaction with the environment during an episode.

• Return: The cumulative reward received by the agent over a trajectory $\tau$.

  • Mathematically:

  $$G(\tau) = \sum_{t=0}^{T} \gamma^t r_t$$

  • Where:
    • $G(\tau)$ is the return for the trajectory when agent follows policy $\pi$
    • $\gamma \in [0,1]$ is the discount factor that determines the present value of future rewards
    • $r_t$ is the reward received at time step $t$
    • $T$ is the final time step in the trajectory

Markov Decision Process (MDP)

A Markov Decision Process (MDP) provides a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly under the control of a decision-maker. The MDP interaction loop follows these steps:

The MDP Interaction Loop

1. Initial State: The environment begins in an initial state $s_0 \in \mathcal{S}$.

2. Agent Observes State: At time step $t$, the agent observes the current state $s_t$ of the environment.

3. Policy Execution: Based on the current state, the agent executes its policy $\pi$:

   • For deterministic policy: $a_t = \pi(s_t)$
   • For stochastic policy: $a_t \sim \pi(\cdot|s_t)$ (action is sampled according to probability distribution)

4. Action Execution: The agent executes the selected action $a_t$ in the environment.

5. State Transition: The environment transitions to a new state $s_{t+1}$ according to the state transition probability: $$s_{t+1} \sim p(\cdot|s_t, a_t)$$

   Where $p(s_{t+1}|s_t, a_t)$ represents the probability of transitioning to state $s_{t+1}$ after taking action $a_t$ in state $s_t$.

6. Reward Generation: The environment generates a reward $r_t$ based on the transition: $$r_t = r(s_t, a_t, s_{t+1})$$

   • $r_t$ is the reward received at time step $t$.

7. Loop Continuation: The process repeats from step 2 with the new state $s_{t+1}$ becoming the current state.

This interaction loop continues either indefinitely (in infinite horizon problems) or until a terminal state is reached (in episodic tasks).

The Markov Property

The key characteristic of an MDP is the Markov property, which states that the future depends only on the current state and action, not on the history of previous states and actions:

$$P(s_{t+1}, r_t | s_t, a_t, s_{t-1}, a_{t-1}, …, s_0, a_0) = P(s_{t+1}, r_t | s_t, a_t)$$

This property simplifies the decision-making process by allowing the agent to consider only the current state when deciding on actions.

What is the aim of Reinforcement Learning?

The fundamental aim of Reinforcement Learning (RL) is to learn an optimal policy that maximizes the expected cumulative reward over time ie return.

Mathematical Formulation

In RL, we seek to find a policy $\pi^*$ such that:

Where:

• $G(\tau)$ is the return for the trajectory when agent follows policy $\pi$
• $\mathbb{E}_{\tau \sim \pi}$ represents the expected value over trajectories $\tau$ generated by following policy $\pi$
• $\sum_{t=0}^{T} \gamma^t r_t$ is the discounted sum of rewards (return)
• $\gamma \in [0,1]$ is the discount factor that determines the present value of future rewards
• $T$ could be finite (episodic tasks) or infinite (continuing tasks)

World Model

A world model in reinforcement learning refers to the agent’s internal representation of how the environment behaves. It captures the dynamics of the environment, allowing the agent to predict future states and rewards based on current states and actions.

Mathematical Formulation

The world model consists of two key components:

1. State Transition Function: This predicts the next state given the current state and action.

   $$P(s_{t+1}|s_t, a_t)$$

   Where:

   • $P$ represents the probability distribution over next states
   • $s_t$ is the current state at time $t$
   • $a_t$ is the action taken at time $t$
   • $s_{t+1}$ is the resulting next state

2. Reward Function: This predicts the expected reward for a state-action-next state transition.

   $$r(s_t, a_t, s_{t+1})$$

   Where:

   • $r$ represents the expected reward
   • $s_t$ is the current state
   • $a_t$ is the action taken
   • $s_{t+1}$ is the resulting next state

Model-Based Reinforcement Learning

In model-based RL, the agent explicitly learns and uses these functions:

$$\hat{P}(s_{t+1}|s_t, a_t) \approx P(s_{t+1}|s_t, a_t)$$ $$\hat{r}(s_t, a_t, s_{t+1}) \approx r(s_t, a_t, s_{t+1})$$

Where $\hat{P}$ and $\hat{r}$ are the agent’s learned approximations of the true dynamics.

The agent can then use these models for:

• Planning future actions by simulating trajectories
• Value estimation without direct environment interaction
• Improving sample efficiency by learning from simulated experiences

Model-Free Reinforcement Learning

In model-free reinforcement learning, the agent learns optimal behavior directly from experience without explicitly modeling the environment dynamics:

• Key Characteristic: The agent does not explicitly learn the state transition function $P(s_{t+1}|s_t, a_t)$ or reward function $r(s_t, a_t, s_{t+1})$.

• Learning Process:

  • The agent collects trajectories $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, …)$ through interaction with the environment
  • These trajectories are used to estimate value functions or directly optimize policies

• Main Approaches:

  • Value-based methods: In value-based methods, we try to learn the quality of individual state or state-action pairs. For example, we can use action-value function $Q(s,a)$ or state-value function $V(s)$ to keep track of average return $G_t$:

    $$Q(s,a) = \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty} \gamma^t r_t \bigg| s_0=s, a_0=a\right]$$ $$V(s) = \mathbb{E}_{a \sim \pi(·|s)}\left[Q(s,a)\right] = \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty} \gamma^t r_t \bigg| s_0=s\right]$$

    where:

    • $Q(s,a)$ is the expected return when taking action $a$ in state $s$ and following policy $\pi$ thereafter
    • $V(s)$ is the expected return when starting in state $s$ and following policy $\pi$
    • $\gamma \in [0,1]$ is the discount factor that balances immediate vs. future rewards
    • $r_t$ is the reward received at time step $t$

  • Policy gradient methods: In policy gradient methods, we do not model the quality of individual state or state-action pairs. Instead, we directly parameterize and optimize the policy itself. Popular methods include Deep Learning based Reinforcement Learning methods like REINFORCE, PPO, TRPO, and Actor-Critic methods.

Bellman Optimality Equation

Theorem

The Bellman Optimality Equation states that the optimal value functionand optimal action-value function satisfy the following recursive equations:

Where:

• $V^*(s)$ is the optimal value of state $s$
• $Q^*(s,a)$ is the optimal action-value of state-action pair $(s,a)$
• $r(s,a,s’)$ is the reward received
• $\gamma$ is the discount factor
• $A(s)$ is the set of available actions in state $s$

Policy Iteration and Value Iteration

Policy Iteration

Policy Iteration is a fundamental algorithm in reinforcement learning for finding an optimal policy in a Markov Decision Process (MDP). It alternates between policy evaluation and policy improvement steps until convergence to the optimal policy.

Intuition Behind Policy Iteration

The core insight of Policy Iteration stems from a simple observation: if we know the exact value of each state under a policy, we can improve that policy by selecting actions that lead to states with higher values. This improvement process, when repeated, eventually leads to the optimal policy.

Mathematical Formulation

Policy Iteration alternates between two key steps:

1. Policy Evaluation

For a fixed policy $\pi$, compute the state-value function $V^\pi(s)$ by solving the Bellman Expectation Equation:

$$V^\pi(s) = \sum_{a} \pi(a|s) \sum_{s’} P(s’|s,a) [r(s,a,s’) + \gamma V^\pi(s’)]$$

Where:

• $\pi(a|s)$ is the probability of taking action $a$ in state $s$ under policy $\pi$

• $P(s’|s,a)$ is the transition probability to state $s’$ from state $s$ taking action $a$

• $r(s,a,s’)$ is the reward received when transitioning from $s$ to $s’$ by taking action $a$

• $\gamma$ is the discount factor that balances immediate versus future rewards

  In practice, this is often solved iteratively:

  1. Initialize $V^\pi(s) = 0$ for all states $s$
  2. Repeat until convergence: $$V^\pi(s) \leftarrow \sum_{a} \pi(a|s) \sum_{s’} P(s’|s,a) [r(s,a,s’) + \gamma V^\pi(s’)]$$

  The solution to this set of equations gives us the true value function for policy $\pi$.

2. Policy Improvement

Update the policy to be greedy with respect to the current value function:

$$\pi’(s) = \arg\max_{a} \sum_{s’} P(s’|s,a) [r(s,a,s’) + \gamma V^\pi(s’)]$$

Or equivalently, using the action-value function $Q^\pi(s,a)$:

$$\pi’(s) = \arg\max_{a} Q^\pi(s,a)$$

Where:

$$Q^\pi(s,a) = \sum_{s’} P(s’|s,a) [r(s,a,s’) + \gamma V^\pi(s’)]$$

This improvement step guarantees that the new policy $\pi’$ is at least as good as $\pi$, and strictly better unless $\pi$ is already optimal.

Value Iteration as an Extreme Case of Policy Iteration

Value Iteration can be viewed as a special case of Policy Iteration where the first step(Policy evaluation) is stopped after just one iteration (instead of running to convergence)

Exploration vs Exploitation

• Challenge: Policy iteration’s greedy improvement step(non deterministic) always selects the action that maximizes expected return based on current value estimates. However, these estimates may be inaccurate initially.

• Exploitation Only Problem: Without exploration, the algorithm might prematurely converge to a suboptimal policy by repeatedly selecting actions based on incomplete or inaccurate value estimates.

• Solution - Epsilon-Greedy: This approach introduces controlled randomness into action selection:

  $$\pi(a|s) = \begin{cases} 1-\epsilon+\frac{\epsilon}{|A(s)|} & \text{if } a = \arg\max_{a’} Q(s,a’) \ \frac{\epsilon}{|A(s)|} & \text{otherwise} \end{cases}$$

  Where:

  • $\epsilon$ is the exploration probability (typically small, e.g., 0.1)
  • $|A(s)|$ is the number of available actions in state $s$
  • With probability $1-\epsilon$, we select the greedy action
  • With probability $\epsilon$, we select a random action

• Benefits: This approach ensures:

  • Sufficient exploration of the state-action space
  • Gradual convergence to the optimal policy as value estimates improve
  • Prevention of getting stuck in local optima

Temporal Difference Learning

The Problem: Learning from Incomplete Episodes

In reinforcement learning, we often face a fundamental challenge: how can an agent learn optimal behavior without waiting for an episode to complete? Traditional methods like Monte Carlo(Gathering information of trajectory till the end) require complete episodes to update value estimates, which is inefficient and sometimes impractical in continuing environments.

The Solution:

Temporal Difference (TD) learning solves this problem by using incremental updates to value estimates after each time step, not just at episode end.

1. Learning value functions ($V$)

$$V(s_t) \leftarrow V(s_t) + \alpha \underbrace{[r_{t+1} + \gamma V(s_{t+1}) - V(s_t)]}_{\text{TD error}}$$

Where:

• $V(s_t)$ is the current estimate of the value function at state $s_t$
• $\alpha$ is the learning rate
• $r_{t+1}$ is the immediate reward
• $\gamma$ is the discount factor
• $V(s_{t+1})$ is the estimated value of the next state
• The term $[r_{t+1} + \gamma V(s_{t+1}) - V(s_t)]$ is called the TD error

2. Learning action values ($Q$) has several important variants, each with specific characteristics and use cases:

• SARSA (State-Action-Reward-State-Action) $$Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha [r_t + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)]$$

  This is an on-policy method that updates Q-values based on actions actually taken under the current policy.

• Expected SARSA $$Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha [r_t + \gamma \sum_{a} \pi(a|s_{t+1})Q(s_{t+1},a) - Q(s_t,a_t)]$$

  This method uses the expected value of the next state-action pair according to the current policy, reducing variance in updates.

• Q-Learning $$Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha [r_t + \gamma \max_{a} Q(s_{t+1},a) - Q(s_t,a_t)]$$

  This is an off-policy(does not need to follow the current policy) method that updates Q-values based on the maximum possible value in the next state, regardless of the action actually taken.

Deep Reinforcement Learning

Enables transition from discrete, low-dimensional state and action spaces to continuous, high-dimensional state and action spaces necessary for real-world tasks

Deep Q-Learning (DQN)

• DQN takes us halfway there - we now have continuous state space but still have discrete action space. This happens because DQN is a value-based method.

• In DQN, a neural network replaces the traditional Q-table, functioning as a function approximator that maps states to action values.

• The network architecture:

  • Input: The state vector $s$ (can be high-dimensional, like pixels from a game screen)
  • Hidden layers: Several fully connected or convolutional layers that extract features from the state
  • Output layer: A vector of size $|A|$ (number of possible actions), where each output node $i$ represents $Q(s,a_i)$

• For a given state $s$, the network performs a forward pass and outputs the Q-values for all actions for that state:

  $$s \rightarrow Neural Network \rightarrow Q(s,a_1), Q(s,a_2), …, Q(s,a_{|A|})$$

• The agent then selects the action with the highest predicted Q-value:

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

• This approach allows us to generalize across similar states and handle continuous state spaces, while still maintaining a discrete action space that can be evaluated simultaneously.

Policy Gradient Methods

The Deep Q-Learning represented the state space as continuous high-dimensional space but still had a discrete low dimensional action space. Policy Gradient Methods represent the action space as continuous high-dimensional space. Moreover, policy gradient methods do not model the quality of individual state or action pairs but instead model the quality of the policy as a whole.

Objective Function ($J(\pi_\theta)$)

The objective function being optimized by the policy gradient methods is denoted as $J(\pi_\theta)$ which takes a policy $\pi_\theta$ parameterized by neural network parameters $\theta$ as input and outputs the expected return.

$J(\pi_\theta)$ can be defined in various ways depending on the problem. Some common formulations include:

• Expected Return: The expected cumulative reward when following policy $\pi_\theta$

  $$J(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\left[G(\tau)\right]$$

• Value of Start State: The value function of the initial state

  $$J(\pi_\theta) = V^{\pi_\theta}(s_0)$$

• Average State Value: The expected value across all states weighted by state visitation frequency $d_\pi(s)$

  $$J(\pi_\theta) = \sum_s d_\pi(s) V^{\pi_\theta}(s)$$

• Average State-Action Value: The expected value across state-action pairs

  $$J(\pi_\theta) = \sum_s d_\pi(s) \sum_a \pi_\theta(a|s) Q^{\pi_\theta}(s,a)$$

Policy Gradient Theorem

To optimize the policy, we need to compute the gradient of the objective function with respect to the policy parameters:

$$\nabla_\theta J(\pi_\theta)$$

The Policy Gradient Theorem provides a general form for this gradient, regardless of which objective function formulation we use:

This elegant formula contains three important components that provide intuition about how policy gradient methods work:

1. $\nabla_\theta \log \pi_\theta(a_t|s_t)$ - How to change parameters: This term indicates how to adjust the policy parameters to increase the probability of action $a$ in state $s$

2. $\sum_{t=0}^{\infty}$ - Average across all states and actions: We average the updates across all timesteps, effectively considering all states and actions based on their frequency of occurrence

3. $\Psi_t$ - How good is action $a$: This measures the quality of the selected action, pushing the policy toward better actions and away from worse ones. It can take different forms depending on the specific algorithm:

• REINFORCE: $\Psi_t = G_t = \sum_{k=t}^{T} \gamma^{k-t} r_k$ (return). It suffers from high variance since it uses the full trajectory return.
• Advantage Actor-Critic: $\Psi_t = A^{\pi_\theta}(s_t, a_t) = Q^{\pi_\theta}(s_t, a_t) - V^{\pi_\theta}(s_t)$ (advantage function). Reduces variance by using a baseline.
• TD Actor-Critic: $\Psi_t = \delta_t = r_t + \gamma V^{\pi_\theta}(s_{t+1}) - V^{\pi_\theta}(s_t)$ (TD error). Uses bootstrapping for lower variance and online updates.

Surrogate Objective Functions

There are also set of algorithms that do not use the objective function $J(\pi_\theta)$ directly but use a surrogate objective function $L(\theta)$ that is a proxy to $J(\pi_\theta)$.

Trust Region Policy Optimization (TRPO)

TRPO is an algorithm that optimizes policies while ensuring the policy doesn’t change too drastically between updates.

Objective Function:

Subject to constraint:

Where:

• $\pi_{\theta_{old}}$ is the policy before the update
• $\pi_\theta$ is the new policy being optimized
• $A^{\pi_{\theta_{old}}}(s,a)$ is the advantage function under the old policy
• $D_{KL}$ is the Kullback-Leibler divergence measuring the difference between policies
• $\delta$ is a small constant that limits how much the policy can change

Intuition: TRPO ensures stable policy updates by constraining the KL divergence between consecutive policies, preventing performance collapse from too large policy changes.

Drawback: Computationally expensive due to second-order optimization methods needed to enforce the KL constraint.

Parameterized as NN: Both policy $\pi_\theta$ and value function $V_\phi$ are parameterized as neural networks.

Proximal Policy Optimization (PPO)

PPO simplifies TRPO while maintaining its benefits of stable policy updates.

Clipped Objective Function:

Where:

• $r_t(\theta) = \frac{\pi_\theta(a|s)}{\pi_{\theta_{old}}(a|s)}$ is the probability ratio between new and old policies
• $\epsilon$ is a small hyperparameter (typically 0.1 or 0.2) that limits how much the policy can change
• $\text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon)$ clips the probability ratio to stay within $[1-\epsilon, 1+\epsilon]$

Intuition: PPO achieves TRPO’s stability without complex constraints by clipping the objective function directly. The clipping discourages large policy updates when they would significantly increase or decrease the probability of advantageous actions.

Advantages:

• Simpler implementation than TRPO
• Better sample efficiency
• Compatible with architectures including recurrent networks
• Can be implemented with first-order optimization methods

Parameterized as NN: Both policy $\pi_\theta$ (actor) and value function $V_\phi$ (critic) are parameterized as neural networks.