Reinforcement Learning

In Reinforcement Learning (RL), we study how an autonomous decision-making Agent can learn to navigate an active Environment to maximize a cumulative mathematical reward signal over time. We formalize this sequential decision-making framework using Markov Decision Processes (MDPs).

An MDP is mathematically defined by a 5-tuple: $(S, A, P, R, \gamma)$:

• State Space ($S$): The set of all possible situations or configurations of the environment.

• Action Space ($A$): The set of all possible choices or moves available to the agent.

• Transition Probability ($P(s' | s, a)$): The probability of transitioning to state $s'$ given that the agent takes action $a$ in state $s$. This represents the dynamics (physics) of the world.

• Reward Function ($R(s, a, s')$): The scalar feedback (reward or penalty) the environment returns after the agent takes a step.

• Discount Factor ($\gamma \in [0, 1)$): Determines how much the agent values immediate rewards compared to future rewards. A value of $\gamma \approx 0$ makes the agent 'shortsighted' (focused only on immediate gains), while $\gamma \approx 1$ makes it highly strategic. It also mathematically guarantees that infinite reward sum sequences converge to a finite limit.

Grid-World Navigation Example: Imagine a robot navigating a $3\times 3$ grid trying to reach a gold chest ($+10$ reward) while avoiding a lava pit ($-10$ penalty). The states $S$ are the $9$ grid coordinates. The actions $A$ are $\{\text{Up, Down, Left, Right}\}$. If the floor is slippery, there might only be an $80\%$ transition probability $P$ of moving in the commanded direction, with a $10\%$ chance of sliding sideways. The robot must learn a sequence of steps that minimizes the risk of slipping into the lava while reaching the gold!

To decide on optimal actions, the agent must learn to estimate the long-term future value of its current choices. We define a Policy $\pi(a | s)$ as the probability distribution of actions given the current state. We evaluate policies using two value functions:

• State-Value Function ($V^{\pi}(s)$): The expected cumulative discounted return starting in state $s$ and following policy $\pi$ thereafter.

• Action-Value Function ($Q^{\pi}(s, a)$): (Known as the Q-value). The expected cumulative discounted return starting in state $s$, executing action $a$, and following policy $\pi$ thereafter.

These functions satisfy recursive, self-consistent relationships called the Bellman Equations. The Bellman Optimality Equation for the optimal Q-value $Q^*(s, a)$ is:

$$Q^*(s, a) = R(s, a) + \gamma \sum_{s'} P(s' | s, a) \max_{a'} Q^*(s', a')$$,

Bellman Backup Example: Suppose we are in a state $s$ and take action $a$. The immediate reward is $R(s, a) = +2$. There is a $100\%$ chance ($P = 1.0$) of transitioning to a next state $s'$. In $s'$, the maximum possible Q-value for any future action is $\max_{a'} Q(s', a') = 10$. If our discount factor is $\gamma = 0.9$, the Bellman backup calculates our current Q-value as: $$Q^*(s, a) = 2 + 0.9 \times (1.0 \times 10) = 2 + 9 = 11$$ This demonstrates beautifully how value information cascades backwards through time steps to guide the agent's current decisions!

How do we solve optimal policies? We use different algorithm classes depending on our data structures:

• Tabular Q-Learning: A model-free, off-policy temporal difference algorithm. It updates a table of Q-values $Q(s,a)$ iteratively without needing to know the environment's transition physics $P$. The update rule is:

$$Q(s, a) \leftarrow Q(s, a) + \alpha \left[ R(s, a) + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$$,

where $\alpha$ is the learning rate. To balance exploration, we use $\epsilon$-greedy selection: the agent takes a random exploratory action with probability $\epsilon$, and exploits its best-known action with probability $1 - \epsilon$.

• Deep Q-Networks (DQN): For high-dimensional state spaces (like raw pixels in Atari games), maintaining a Q-table is impossible. DQNs solve this by replacing the lookup table with a Neural Network $Q(s, a; \theta)$ to approximate optimal Q-values.

• Policy Gradients & Actor-Critic: Instead of approximating Q-values, policy gradient methods directly parameterize and optimize the policy $\pi_\theta(a|s)$ using gradient ascent. Actor-Critic architectures combine both: the Critic approximates value functions to evaluate actions, while the Actor updates the policy direction based on the Critic's feedback.