Problem 640183 · hard · Level 06 Heuristics & Optimization

The Robot Learns Its Way Around the Pit

Q-learning · reinforcement learning · epsilon-greedy · exploration schedule · grid world · Bellman equation

A robot moves on a grid given as a list of equal-length strings: S is its start (exactly one), G the goal, P a pit, # a wall and . free floor. Its moves are ^, v, < and > (up, down, left, right). A move into a wall or off the grid leaves it where it is. Entering G gives reward +10 and ends the episode, entering P gives -10 and ends it, and every other move (including a blocked one) gives -1.

Write grid_q_learning(grid, episodes, max_steps, alpha, gamma, epsilon, seed) that learns a table Q[(cell, move)] (all values start at 0.0) and returns a tuple (policy, steps, start_value). Use one rng = random.Random(seed) and run exactly this schedule:

  1. Episode e (counting from 0) starts at S and uses the exploration rate eps = epsilon · (episodes - e) / episodes.
  2. Each step: if rng.random() < eps, the move is rng.choice("^v<>"); otherwise it is the greedy move, the one with the highest Q value in the current cell (compare the values rounded to 9 decimal places; on a tie take the first in the order ^, v, <, >).
  3. Make the move, then update Q[(cell, move)] ← Q + alpha · (target - Q), where target is the reward if the episode ended, and otherwise the reward plus gamma times the largest Q value of the new cell.
  4. The episode ends when the robot enters G or P, or after max_steps steps.

steps is the list of the number of steps of every episode. policy is the grid with every G, P and # kept and every other cell (including S) replaced by its greedy move. start_value is the largest Q value of the start cell at the end.

Examples

Input:  grid = ["S.G"], episodes = 2, max_steps = 10, alpha = 0.5, gamma = 0.9, epsilon = 0.0, seed = 1
Output: ([">>G"], [10, 2], -0.75)
Explanation: in the first episode untried moves (value 0) always look best, so the robot tries
^, v, < (blocked) and > at the start, then ^, v and < in the middle (< takes it back), then the
three blocked moves at the start again, and its 10th step reaches the middle. In the second
episode > is the best move in both cells and the robot walks straight to the goal.

Input:  grid = ["...G", ".#.P", "S..."], episodes = 300, max_steps = 50, alpha = 0.5, gamma = 0.9,
        epsilon = 0.3, seed = 0
Output: policy ['>>>G', '^#^P', '>>^<'], steps starting [23, 30, 13, 12, 24, 6, ...] and ending
        [..., 5, 5, 5, 5, 5, 5], start_value 3.121999999999999
Explanation: the robot learns the 5-step route along the bottom row and up the third column,
avoiding the pit; 3.122 = -1 - 0.9 - 0.81 - 0.729 + 0.9⁴ · 10.

Constraints

  • grids of 1 to 8 rows and 1 to 12 columns, 1 <= episodes <= 1000, 1 <= max_steps <= 200
  • 0 < alpha <= 1, 0 <= gamma <= 1, 0 <= epsilon <= 1
  • floats are compared with a tolerance of 1e-6

Goals

  • Implement tabular Q-learning on a grid world with walls, a goal and pits
  • Explore epsilon-greedily with an exploration rate that decreases episode by episode
  • Read the learned policy off the table and check the start value against the Bellman equation
Starting Python…