Lesson 4: Q-Learning Deep Dive & Multi-Armed Bandits

Reinforcement Learning: From Basics to Advanced

Part 1: RL Foundation — Markov Decision Process & Tabular Methods

xdev.asia

Introduction

Q-Learning is the off-policy TD control algorithm — the foundation for DQN and all value-based deep RL. Multi-Armed Bandits is a simplified RL focusing on exploration vs exploitation.

---

1. Q-Learning Algorithm

def q_learning(env, num_episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = np.zeros((env.observation_space.n, env.action_space.n))
    
    for episode in range(num_episodes):
        state, _ = env.reset()
        done = False
        
        while not done:
            # ε-greedy action selection
            if np.random.random() < epsilon:
                action = env.action_space.sample()
            else:
                action = np.argmax(Q[state])
            
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            
            # Q-Learning update (off-policy: max over next actions)
            Q[state, action] += alpha * (
                reward + gamma * np.max(Q[next_state]) * (1 - done) - Q[state, action]
            )
            state = next_state
    return Q

SARSA vs Q-Learning

	SARSA	Q-Learning
Type	On-policy	Off-policy
Update	Q(s,a) += α[r + γQ(s',a') - Q(s,a)]	Q(s,a) += α[r + γ max Q(s',·) - Q(s,a)]
Behavior	Safer, follows ε-greedy	Learns optimal policy

---

2. Exploration Strategies

ε-greedy with Decay

def epsilon_greedy_decay(Q, state, episode, min_epsilon=0.01, decay=0.995):
    epsilon = max(min_epsilon, 1.0 * (decay ** episode))
    if np.random.random() < epsilon:
        return env.action_space.sample()
    return np.argmax(Q[state])

Boltzmann (Softmax) Exploration

def boltzmann_action(Q, state, temperature=1.0):
    q_values = Q[state] / temperature
    probs = np.exp(q_values - np.max(q_values))
    probs /= probs.sum()
    return np.random.choice(len(probs), p=probs)

---

3. Multi-Armed Bandit

Simplified RL: 1 state, K actions (arms), maximize reward.

class MultiArmedBandit:
    def __init__(self, k=10):
        self.k = k
        self.true_values = np.random.randn(k)
    
    def pull(self, arm):
        return np.random.randn() + self.true_values[arm]

class UCBAgent:
    def __init__(self, k, c=2.0):
        self.counts = np.zeros(k)
        self.values = np.zeros(k)
        self.c = c
        self.t = 0
    
    def select_arm(self):
        self.t += 1
        if 0 in self.counts:
            return np.argmin(self.counts)
        ucb = self.values + self.c * np.sqrt(np.log(self.t) / self.counts)
        return np.argmax(ucb)
    
    def update(self, arm, reward):
        self.counts[arm] += 1
        self.values[arm] += (reward - self.values[arm]) / self.counts[arm]

---

4. Hands-on: Taxi Environment

env = gym.make("Taxi-v3")
Q = q_learning(env, num_episodes=10000, alpha=0.1, gamma=0.99, epsilon=0.1)

# Test learned policy
state, _ = env.reset()
total_reward = 0
for _ in range(200):
    action = np.argmax(Q[state])
    state, reward, done, _, _ = env.step(action)
    total_reward += reward
    if done:
        break
print(f"Total reward: {total_reward}")

---

Summary

Strategy	Advantages	Disadvantages
ε-greedy	Simple, effective	Uniform random exploration
ε-decay	Balances explore/exploit	Need to tune decay rate
UCB	Principled, no ε	Deterministic
Thompson	Bayesian optimal	Computational costs
Boltzmann	Smooth, temperature control	Sensitive to scale