Machine Learning Algorithms 3: Reinforcement Learning

Reinforcement Learning is an area of machine learning concerned with how intelligent agents ought toto take actions in an environment in order to maximize a cumulative reward. It is a goal-oriented learning paradigm where an agent learns from the consequences of its actions, rather than from being explicitly taught.

Key Concepts

• Agent: The learner or decision-maker.
• Environment: The external world in which the agent operates.
• State (s): A snapshot of the environment at a particular time.
• Action (a): A move made by the agent, which causes a change in the environment's state.
• Reward (r): A scalar feedback signal from the environment that indicates how good or bad an action was. The agent's goal is to maximize the cumulative reward.
• Policy (π): The agent's strategy, which maps states to actions. It defines the agent's behavior.
• Value Function (V(s) or Q(s, a)): A function that estimates the expected future reward from a given state or state-action pair. It represents the "long-term value".
• Model: An internal representation of the environment's dynamics, which predicts the next state and reward given a current state and action. RL algorithms can be model-free or model-based.

Covered Algorithms

• Q-Learning
• Deep Q-Networks (DQN)
• Policy Gradients
• Actor-Critic Methods

Q-Learning

Q-Learning is a foundational model-free, off-policy reinforcement learning algorithm. It aims to learn a policy that tells an agent the best action to take in a given state.

• Model-Free: It learns directly from experience (rewards and states) without needing a model of the environment.
• Off-Policy: It can learn the optimal policy even while following a different, exploratory policy (e.g., taking some random actions).

How it works: The Q-Table

Q-Learning works by maintaining a Q-table, a matrix where rows represent states and columns represent actions. Each cell Q(s, a) in this table stores the Q-value, which is the expected future reward for taking action a in state s.

The agent learns these Q-values iteratively using the Bellman equation. The update rule for a Q-value is: Q(s, a) ← Q(s, a) + α * [r + γ * max_a' Q(s', a') - Q(s, a)]

Where:

• s, a: Current state and action.
• s', r: Next state and reward after taking action a.
• α (alpha): The learning rate, controlling how much new information overrides old information.
• γ (gamma): The discount factor, which values future rewards. A value close to 1 prioritizes long-term rewards.
• max_a' Q(s', a'): The maximum Q-value for the next state s', representing the best possible future reward from that state.

Exploration vs. Exploitation

A key challenge in RL is balancing exploitation (taking the best-known action) with exploration (trying new actions to discover better rewards). Q-Learning often uses an epsilon-greedy strategy: with probability epsilon, the agent takes a random action; otherwise, it takes the action with the highest Q-value.

Deep Q-Networks (DQN)

Deep Q-Networks (DQN) extend Q-Learning to handle environments with high-dimensional state spaces (like video game screens), where a Q-table would be impossibly large. It achieves this by using a deep neural network to approximate the Q-value function, Q(s, a; θ) ≈ Q*(s, a).

The network takes the state as input and outputs the Q-values for all possible actions in that state.

Key Innovations

DQN introduced two key techniques to stabilize the learning process, which is notoriously difficult when using neural networks for RL:

1. Experience Replay: The agent's experiences (s, a, r, s') are stored in a large replay buffer. Instead of training on consecutive experiences (which are highly correlated), the network is trained on a random mini-batch sampled from this buffer. This breaks temporal correlations and improves data efficiency.
2. Target Network: The Bellman equation creates a problem where the target (r + γ * max_a' Q(s', a')) is constantly changing because the same network is used to predict both the current and target Q-values. To solve this, DQN uses a second, separate target network to calculate the target Q-values. The target network's weights are frozen for a period and then periodically updated with the weights of the main Q-network, which provides a more stable learning target.

Policy Gradients

Policy Gradient methods are a class of RL algorithms that learn the policy π(a|s; θ) directly, without needing to learn a value function first. The policy is parameterized by θ (e.g., the weights of a neural network) and is typically stochastic, outputting a probability distribution over actions.

How it works

The goal is to find the policy parameters θ that maximize the expected total reward. This is done by performing gradient ascent on an objective function J(θ).

The core idea is to adjust the policy parameters θ in the direction that makes "good" actions more likely and "bad" actions less likely. The Policy Gradient Theorem provides an expression for the gradient of the objective function: ∇_θ J(θ) ∝ Σ [Σ ∇_θ log π(a|s; θ) * A(s, a)]

• ∇_θ log π(a|s; θ): This term, the "score function," tells us the direction to adjust the parameters θ to increase the probability of taking action a in state s.
• A(s, a): This is an advantage function that weights the update. It measures how much better or worse the chosen action a was compared to the average action in that state. A common choice is A(s, a) = R_t - V(s), where R_t is the cumulative future reward and V(s) is a learned value function baseline.

The most basic policy gradient algorithm is REINFORCE, which uses the total return of an episode as the advantage term.

Advantages over Value-Based Methods (like DQN)

• Can learn stochastic policies, which is useful in environments where the optimal policy is random.
• Better convergence properties in many cases.
• Can handle continuous action spaces more naturally.

Actor-Critic Methods

Actor-Critic methods are a hybrid approach that combines the strengths of both policy-based (Policy Gradients) and value-based (Q-Learning) methods. They consist of two components, typically both neural networks:

1. The Actor (Policy): Controls how the agent behaves. It learns and updates the policy π(a|s; θ).
2. The Critic (Value Function): Measures how good the actor's actions are. It learns and provides an estimate of a value function (e.g., V(s) or Q(s, a)).

The Learning Loop

1. The Actor observes a state s and chooses an action a based on its policy.
2. The agent receives a reward r and transitions to a new state s'.
3. The Critic evaluates the action by computing an advantage signal, typically the TD Error: δ = r + γ * V(s') - V(s). This error tells the Actor whether the outcome was better (δ > 0) or worse (δ < 0) than expected.
4. The Actor updates its policy parameters θ using the policy gradient, weighted by the Critic's TD error.
5. The Critic updates its value function parameters using the same TD error, improving its ability to evaluate the Actor's future actions.

This approach is more stable than pure Policy Gradients because the Critic's value estimate provides a lower-variance signal for the Actor to learn from.

Key Variants

• A3C (Asynchronous Advantage Actor-Critic): Uses multiple worker agents in parallel to explore the environment, providing a stream of diverse experiences that helps stabilize training.
• PPO (Proximal Policy Optimization): A state-of-the-art method that improves training stability by using a clipped objective function to prevent the policy from changing too drastically in one update.
• SAC (Soft Actor-Critic): An off-policy actor-critic algorithm based on the maximum entropy framework. It encourages exploration by adding an entropy term to its objective, leading to highly efficient and robust performance, especially in continuous control tasks.