Exercise 8.1.2

Dyna-Q vs n-step bootstrapping in the Dyna maze

MediumWritten

Consider a reinforcement learning agent in a simple, deterministic maze composed of 47 states, shown in Figure 1. From any state, the agent can take four actions: up, down, left, or right. An action deterministically takes the agent to the corresponding neighboring state, unless that movement is blocked by an obstacle or the maze edge, in which case the agent remains in its current state.

The agent’s task is to find the shortest path from a start state (S) to a goal state (G). A reward of +1 is given for transitioning into the goal state, and a reward of 0 is given for all other transitions. After reaching the goal, the agent is reset to the start state to begin a new episode. The task is discounted with \(\gamma = 0.95\), and the agent uses a step-size parameter of \(\alpha = 0.1\) and an \(\epsilon\)-greedy policy with \(\epsilon = 0.1\) for exploration.

When selecting greedily among actions, ties were broken randomly. The agents varied in the number of planning steps, n, they performed per real step. For each n, the curves show the number of steps taken by the agent to reach the goal in each episode, averaged over 30 repetitions of the experiment. In each repetition, the initial seed for the random number generator was held constant across algorithms. Because of this, the first episode was exactly the same (about 1700 steps) for all values of n, and its data are not shown in the figure.

We compare two methods for solving this task: a non-planning method, which is standard one-step Q-learning (equivalent to the Dyna-Q algorithm with zero, or \(n=0\), planning steps), and a planning method, which is the Dyna-Q algorithm with fifty (\(n=50\)) planning steps performed after each real step in the environment.

Figure 1 shows the learning curves for these agents, demonstrating that planning significantly speeds up learning. Figure 1 provides a snapshot of the policies learned by both agents halfway through the second episode. The non-planning method looks particularly poor because its one-step updates have propagated very little information from the goal.

Question: Given this context, do you think one of the multi-step bootstrapping methods, like n-step TD or n-step SARSA, could learn a policy as effectively and rapidly as the Dyna-Q method with \(n=50\) planning steps in this scenario? Explain why or why not, referring to the underlying mechanisms of each approach.

fig82.pngfig83.png
Figure 1: The Dyna Maze environment and average learning curves for Dyna-Q agents with varying numbers of planning steps (\(n\)) per real step. The task is to travel from S to G.

Source: Sutton & Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., Exercise 8.1; Example 8.1. Figure 8.2 is redrawn from a new run of the book's experiment. Figure 8.3 is redrawn from the book. Licensed CC BY-NC-ND 2.0.