Week 2 value-based reinforcement learning approach

[Key objectives]

• Understand how the Q-function (Q-value) defines the value of state–action pairs and is updated using the Bellman equation

• Prepare to implement a neural network model that approximates the Q-function with PyTorch

[Value-Based Reinforcement Learning (Value-based Approach)]

Learn a value function or Q-function without directly parameterizing the policy

1. $Q$ function — $Q(s, a)$

• The expected cumulative reward (expected return) from taking action a in state s

• Quantify “How good is taking action a in state s?” Knowing the Q-function exactly makes it easy to construct a policy that selects the highest-value action in each state

2. $Q$-learning ($Q$-learning)

• Update the Q-function using the Bellman optimality equation

• $Q^*(s,a) = \mathbb{E}[ r + \gamma \max_{a'} Q^*(s', a') ]$

  • $s'$: Next state
  • $r$: Reward
  • $\gamma$: Discount factor (0–1)
  • $\max_{a'}$: Select the action with the highest Q-value in the next state.

• $Q$-learning: an off-policy algorithm that updates the Q-function using the Bellman optimality equation

  • Update rule $$Q(s,a) \leftarrow Q(s,a) + \alpha [ r + \gamma \max_{a'}Q(s',a') - Q(s,a) ]$$
    • $\alpha$: learning rate
    • $(s, a, r, s')$: experience sample

3. Prepare to implement a neural network model in PyTorch

• Approximate the Q-function with a deep neural network for scalability in complex environments
• Next, introduce replay buffers and target networks to implement DQN and actually train the Q-function

[Q-learning example: Escape a maze with Q-learning]

1. Environment setup

Define the maze

Represent a 5x5 maze as a NumPy array

• 0: path
• 1: wall
• 2: start
• 3: goal

import numpy as np

# Set up a 5x5 maze (0: path, 1: wall, 2: start, 3: goal)
maze = np.array([
    [2, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 1, 0, 3, 0]
])

Action definition

Define the actions available to the agent

• 0: Up
• 1: Down
• 2: left
• 3: Right

# 0: Move up 1 cell (-1,0)
# 1: Move down 1 cell (1,0)
# 2: Move left 1 cell (0,-1)
# 3: Move right 1 cell (0,1))
actions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

Initialize the Q-table

Initialize the Q-table to 0 (5x5x4 actions).

q_table = np.zeros((5, 5, 4))

Hyperparameter settings

Set the hyperparameters needed for training.

• learning_rate: Learning rate
• discount_factor: Discount factor
• epsilon: exploration rate
• episodes: Number of episodes

learning_rate = 0.1
discount_factor = 0.9
epsilon = 0.1  # Exploration rate
episodes = 1000

2. Q-learning algorithm

Obtain the next state

Function that takes the current state and action and returns the next state

def get_next_state(state, action):
  next_state = (state[0] + actions[action][0], state[1] + actions[action][1])

  # Check boundaries and detect wall collisions
  if 0 <= next_state[0] < 5 and 0 <= next_state[1] < 5 and maze[next_state[0], next_state[1]] != 1:
    return next_state
  else:
    return state

Obtain reward

A function that takes the current state and returns a reward

• Goal state: 10
• Otherwise: -1

def get_reward(state):
  if maze[state[0], state[1]] == 3:
    return 10
  else:
    return -1

Q-learning training

Update the Q-table using Q-learning.

# Q-learning algorithm
for episode in range(episodes):
  state = (0, 0)  # Starting position
  while maze[state[0], state[1]] != 3 :
    if np.random.rand() < epsilon:
        action = np.random.randint(4)
    else:
        action = np.argmax(q_table[state[0], state[1], :])

    next_state = get_next_state(state, action)
    reward = get_reward(next_state)

    q_table[state[0], state[1], action] += learning_rate * (
            reward + discount_factor * np.max(q_table[next_state[0], next_state[1], :])
            - q_table[state[0], state[1], action]
    )

    state = next_state

    # Print progress (example: every 100 episodes)
  if (episode + 1) % 100 == 0:
    print(f"Episode {episode + 1} 완료")

Episode 100 완료
Episode 200 완료
Episode 300 완료
Episode 400 완료
Episode 500 완료
Episode 600 완료
Episode 700 완료
Episode 800 완료
Episode 900 완료
Episode 1000 완료

Q-value update formula

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

• $Q(s, a)$: Q-value in state $s$ of action $a$
• $\alpha$: learning rate
• $r$: reward
• $\gamma$: discount factor
• $\max_{a'} Q(s', a')$: maximum Q-value at the next state $s'$

3. Check results

Find the final path

Use the learned Q-table to find the optimal path from the initial state to the goal state.

# Find the final path
state = (0, 0)
path = [state]
while maze[state[0], state[1]] != 3:
    action = np.argmax(q_table[state[0], state[1], :])
    state = get_next_state(state, action)
    path.append(state)

Path visualization

Print a text visualization of the path found

# Visualize the path
print("미로 탈출 경로:")
for i in range(5):
    for j in range(5):
        if (i, j) == (0, 0):
          print("S", end=" ")
        elif (i,j) == (4,3):
          print("G", end=" ")
        elif (i,j) in path:
          print("*", end=" ")  # Path taken
        elif maze[i, j] == 1:
            print("#", end=" ")  # Mark walls
        else:
            print(" ", end=" ")
    print()

미로 탈출 경로:
S         
* # #     
* * * #   
# # * #   
  # * G