Q-Learning

Tags: #◇Computer Science #◇CSINTSY #◇Q-Learning #◇Problem Solving #◇M6

---

◇Overview

Q-Learning is a Reinforcement Learning algorithm used when the agent does not know the transition probabilities or the reward distribution of an environment beforehand. Because the agent lacks a model of the world (unlike in MDPs), it must learn the optimal policy by exploring the environment and experiencing the rewards and transitions firsthand.

Q-Table:
The algorithm uses a lookup table (Q-table) to store the estimated Q-values for every state-action pair. The Q-value represents the expected total cumulative reward of taking a specific action from a specific state and acting optimally thereafter.

Exploration vs. Exploitation:
During training, the agent faces a trade-off: Exploration: Taking random actions to discover new states and potentially higher rewards. Exploitation: Choosing the best-known action based on current Q-values to maximize reward.
Typically, agents start with high exploration and gradually shift to exploitation as they learn the environment.

Deep Q-Learning:
For environments with vast or continuous state spaces, maintaining a Q-table becomes impossible. Deep Q-Learning replaces the Q-table with a deep neural network that approximates the Q-value for any given state-action pair.

◇Important Formulas

Q-Learning Update Rule:
When an agent takes action $a$ in state $s$, transitions to state $s'$, and receives reward $R$, the Q-value is updated:
$Q(s, a) \leftarrow (1 - \alpha) Q(s, a) + \alpha \left( R + \gamma \max_{a'} Q(s', a') \right)$
Where: $\alpha$ is the learning rate. $\gamma$ is the discount factor. $\max_{a'} Q(s', a')$ is the highest expected reward from the next state $s'$.

◇Worked Examples

Frozen Lake Problem:
An agent must navigate a slippery grid from start to goal without falling into holes. The agent intends to move 'Up', but there is a chance it slips 'Left' or 'Right'. Training:

1. Initialize Q-table to 0.
2. The agent picks an action (randomly or optimally).
3. The agent observes the outcome state and reward.
4. The Q-table is updated using the outcome.
5. Repeat until the end of the episode. Over hundreds of episodes, the agent's Q-table converges, and the optimal policy naturally avoids holes and slippery edges leading to danger.

◇References & Navigation

• Previous Topic: ◇Markov Decision Processes
• Next Topic: ◇State Based Model
• Related Notes: ◇Q Learning