• Introduction
• Getting Started (Python setup, type annotations, style, autograding)
• Part 1: Value Iteration (35 points) — Q1, Q2
• Part 2: Q-Learning (70 points) — Q3, Q4, Q5, Q6, Q7, Q8
• Part 3: Report (40 points) — Q9
• What to Turn In
• Updates and Corrections

This assignment not only offers an opportunity to implement the Value Iteration algorithm, but also an opportunity to see how reinforcement learning techniques can be applied to problem solving of the sort we studied earlier with state-space search.

The interactions between a problem-solving agent and its problem-domain environment are modeled probabilistically using the technique of Markov Decision Processes (MDPs). Within this framework, the assignment focuses on two approaches to having the agent maximize its expected utility: (A) by a form of planning, in which we assume that the parameters of the MDP (especially the transition model T and the reward function R) are known, which takes the form of Value Iteration, and (B) by an important form of reinforcement learning, called Q-learning, in which we assume that the agent does not know the MDP parameters.

The particular MDPs we are working with in this assignment are variations of a “TOH World”, meaning Towers-of-Hanoi World. We can think of an agent as trying to solve a TOH puzzle instance by wandering around in the state space that corresponds to that puzzle instance. If it solves the puzzle, it will get a big reward. Otherwise, it might get nothing, or perhaps a negative reward for wasting time. In Part 1, the agent is allowed to know the transition model and reward function. In Part 2, the agent is not given that information, but has to learn about good policies by exploring and seeing what states it can get to and how good they seem to be based on what rewards it can get and where states seem to lead to.

Figure 1. An early description of the problem “La Tour d’Hanoi” from the 1895 book by Edouard Lucas. Your program will determine an optimal policy for solving this puzzle, as well as compute utility values for each state of the puzzle.

The starter code contains these files:

• Files you’ll edit:
  • solver_utils.py — utilities for the reinforcement learning algorithms (all of your code goes here).
  • a5_report.txt — the template for your report.
• Files you should read but NOT edit:
  • solvers.py — reinforcement learning solvers for MDPs.
  • toh_mdp.py — definitions for the TOH-world MDP.
• Files you will not edit:
  • autograder.py — the assignment autograder.
  • gui.py — graphical user interface for the TOH-world MDP.
  • test_cases/ — test cases used by the autograder.

Download and unzip the starter code. We recommend Python 3.14 (3.10 or later is the minimum), with the Tkinter user-interface library available (it is included with the standard Python.org installers).

In a command line, run

python gui.py

This will start up a graphical user interface, which can help you debug. You can see that some menus are provided. Some menu choices are handled by the starter code, such as setting some parameters of the MDP. However, you will need to implement the code to actually run Value Iteration and Q-learning, and some menu items will not work correctly until you implement the corresponding functions.

A Note on Python Type Annotation. Most of the starter code that you will be interacting with is annotated with types. Python is a dynamically typed language, which makes it flexible and good for prototyping, but any type checking happens only at runtime, so it can be hard to know what kind of arguments a function expects, and type errors can be hard to track down. The type annotations in the starter code are there to help you determine what’s an appropriate input to each function. If you use an IDE with good support for static inference, such as PyCharm, you’ll see an error if your code doesn’t type check. For a quick introduction to type annotation, see this cheat sheet. If you wish to type-check your code, you can install the mypy type checker with pip install mypy and check your solution file with

mypy solver_utils.py

Note that mypy will report many errors if you haven’t completed all the questions. You may want to add some temporary return values to suppress these errors before you actually implement those functions.

A Note on Style. With a handful of exceptions, the starter code complies with the official Python style guide PEP 8 and the Google Python Style Guide. We encourage you to follow the same conventions. If you use PyCharm, PEP 8 violations will be pointed out to you.

Autograding. The included autograder has a number of options. You can view them with

python autograder.py --help

Some commonly used options are: --no-graphics, which disables displaying the GUI; -q, which grades only one question (e.g., -q q1); and -p, which grades only one part (e.g., -p p1). Gradescope runs the same kinds of tests as the local autograder, plus some additional hidden test cases, so passing all the local tests is a good sign but not a guarantee of full credit.

Part 1 is concerned with Value Iteration. Now would be a good time to review the Bellman equations. You can test your Part 1 implementations with

python autograder.py -p p1

Q1: Value Iteration (25 points)

In solver_utils.py, complete the function that computes one step of value iteration:

def value_iteration(
        mdp: tm.TohMdp, v_table: tm.VTable
) -> Tuple[tm.VTable, tm.QTable, float]:

Before you write any code, it would be a good idea to take a look at the toh_mdp.py file, which defines all the components of the TOH-world MDP. In particular, TohState, Operator, TohAction, and most importantly, TohMdp are the classes you will interact with the most, and you should familiarize yourself with the way these objects interact with each other. When in doubt about the details of any functionality, consult the documentation (provided as comments in the code) and the implementation itself; the comments also point out some common pitfalls.

You can test your implementation with

python autograder.py -q q1

The autograder will display your value iteration process for a sample TOH MDP. You might notice that the autograder logs lots of additional info. You can suppress this by setting LOGLEVEL from INFO to WARNING in your shell, e.g.,

LOGLEVEL=WARNING python autograder.py -q q1

Note: Our reference solution takes 12 lines.

Q2: Extracting a Policy (10 points)

In solver_utils.py, complete the function that extracts a policy from the Q-value table:

def extract_policy(
        mdp: tm.TohMdp, q_table: tm.QTable
) -> tm.Policy:

You can test your implementation with

python autograder.py -q q2

The autograder will display your value iteration process for a sample TOH MDP as well as the policy during each iteration. You can observe how the policy changes as the values change. Finally, the autograder will simulate an agent’s movement using your extracted policy. If your implementation is correct, your agent mostly follows the optimal trajectory. You can view the optimal path by selecting “MDP Rewards” → “Show golden path (optimal solution)”.

Note: Our reference solution takes 2 lines.

You can test your Part 2 implementations with

python autograder.py -p p2

For each of Q5 through Q8, half of the points come from quick checks of your functions (described with each question), and the other half come from a Q-learning run that uses them. Unless stated otherwise, these runs use the 3-disk MDP with 20% noise and a discount factor of 0.9, and you receive full credit for the run if your agent learns the optimal policy on the solution path (it’s OK if the policy for other states is suboptimal).

Q3: Q-Update (20 points)

Q-learning performs an update on the Q-value table upon observing a transition, which in this case is represented as an (s, a, r, s′) tuple. Implement the q_update function, which updates the q_table based on the observed transition, with the specified learning rate alpha:

def q_update(
        mdp: tm.TohMdp, q_table: tm.QTable,
        transition: Tuple[tm.TohState, tm.TohAction, float, tm.TohState],
        alpha: float) -> None:

You can test your implementation with

python autograder.py -q q3

Note: Our reference solution takes 5 lines.

Q4: Extracting a Value Table from a Q-Value Table (10 points)

Q-learning only works with the Q-value table, but sometimes it is useful to know the (estimated) value of a state. Implement the extract_v_table function, which computes a value table from the Q-value table:

def extract_v_table(mdp: tm.TohMdp, q_table: tm.QTable) -> tm.VTable:

You can test your implementation with

python autograder.py -q q4

Note: Our reference solution takes 2 lines.

Q5: ε-Greedy Action Selection (10 points)

At the core of Q-learning is the exploration strategy, and ε-greedy is a commonly used baseline method. In this assignment, your agent performs active reinforcement learning: it chooses its own next action while acting and learning, instead of passively learning by observing a sequence of transitions chosen by someone else. Implement choose_next_action:

def choose_next_action(
        mdp: tm.TohMdp, state: tm.TohState, epsilon: float, q_table: tm.QTable,
        epsilon_greedy: Callable[[List[tm.TohAction], float], tm.TohAction]
) -> tm.TohAction:

Make sure you use the supplied epsilon_greedy function to sample the action. You should not need to use the random module; that is handled for you in the QLearningSolver.epsilon_greedy method in solvers.py. Make sure you read its code.

Pass epsilon_greedy the list of all actions that tie for the highest Q-value in the given state. You may detect ties either with exact equality (==) or with math.isclose(); the autograder accepts either.

You can test your implementation with

python autograder.py -q q5

The autograder will first check your implementation on a set of Q-value tables, and then use it to run 10,000 Q-learning steps with ε = 0.2.

Note: Our reference solution takes 4 lines.

Q6: Custom Epsilon (10 points)

If you use a constant ε, your agent will keep wasting time exploring unnecessary states long after it has learned a good policy. A common way to mitigate this is to make ε a function of the time step that decreases over time. For example, see the “How to Explore?” slide in our Q-Learning lecture slides, or, for more detail, slides 44–46 on GLIE: Greedy in the Limit with Infinite Exploration in this PowerPoint presentation (UW sign-in required). Implement custom_epsilon to define your function of ε:

def custom_epsilon(n_step: int) -> float:

Your custom_epsilon must meet these requirements, which the autograder checks (both the local autograder and Gradescope):

• For every n_step from 1 to 10,000, it returns a value between 0.0 and 1.0 (inclusive).
• custom_epsilon(1) >= 0.1 (enough exploration at the start).
• custom_epsilon(10000) <= 0.1 (little exploration by the end).
• It returns at least 10 different values for n_step from 1 to 1,000 (i.e., it actually changes over time).

To activate your custom epsilon schedule, set solver.use_custom_epsilon = True and solver.epsilon = None on a QLearningSolver instance. You can test your implementation with

python autograder.py -q q6

As in Q5, the autograder will then use your custom ε function to run 10,000 Q-learning steps.

Note: Our reference solution takes 1 line.

Q7: Exploration Function (10 points)

While ε-greedy Q-learning uses randomness to control exploration, it is also possible to guide exploration more systematically. One way to do this is with “exploration functions” that give the agent an incentive to explore parts of the state space that have not been visited as much as others. (See the “Exploration Functions” slide, slide 19, in the Q-Learning lecture slides.)

Implement two functions in solver_utils.py. First, implement the exploration function itself, which returns an optimistically adjusted value for a Q-state based on its Q-value u and how many times it has been visited, n:

def exploration_fn(u: float, n: int) -> float:

We strongly recommend this form, which uses a slowly decreasing bonus: return u + R_plus / math.sqrt(n + 1), where R_plus is an optimistic upper bound on any achievable reward. R_plus is a constant that you choose; a value around the size of the goal reward (e.g., 100) works well. This ensures under-explored Q-states always receive a positive bonus that shrinks as visits accumulate, so the agent never locks into a greedy policy before the Q-values have converged.

The lecture slides (adapted from UC Berkeley's CS 188) show a simpler and more intuitive form, f(u, n) = u + k/n. It typically works less well in this assignment: a bonus proportional to 1/n shrinks quickly (after only 4 visits it is down to a quarter of its size, while 1/√n is still at half), so the agent can stop exploring before it has found the best path, especially when k is small compared with the rewards (the slides' example uses k = 5, while reaching the goal is worth 100). It is also undefined when n = 0. The square-root form keeps exploration going longer; the same idea appears in the “upper confidence bound” methods used in practice.

Whatever form you use, the autograder checks that, for a fixed u, the value of exploration_fn(u, n) never increases as n increases, and that for a very large n (e.g., one million) it is close to u.

Then implement the action-selection function that uses it:

def choose_next_action_with_exploration_fn(
        mdp: tm.TohMdp, state: tm.TohState, q_table: tm.QTable,
        visit_counts: Dict[Tuple[tm.TohState, tm.TohAction], int],
        exploration_fn: Callable[[float, int], float]
) -> tm.TohAction:

This function should pick the action that maximizes exploration_fn(Q(state, action), visit_counts[(state, action)]) over every action in mdp.actions, including 'Exit' (its Q-value is learned like any other action's), calling exploration_fn once for each action and treating a missing visit count as 0. Then increment visit_counts[(state, chosen_action)] before returning. When multiple actions tie for the highest adjusted value, break ties randomly (e.g., using random.choice()). The visit_counts dictionary is maintained for you in solvers.py (do not edit solvers.py). To activate this exploration strategy, set solver.use_exploration_fn = True on a QLearningSolver instance.

You can test your implementation with

python autograder.py -q q7

The autograder will check exploration_fn and choose_next_action_with_exploration_fn, and then run 5,000 Q-learning steps (3 disks, no noise, α = 0.1).

Note: Our reference solution takes 1 line for exploration_fn and 4 lines for choose_next_action_with_exploration_fn.

Q8: Custom Alpha, the Learning Rate (10 points)

Design and implement a scheme for gradually lowering the value of α (the learning rate) that is used in the Q-update formula. The purpose of starting with a relatively high value (close to 1) and gradually lowering it is to obtain plausible Q-value estimates quickly (rather than the zeros with which they were initialized), but, over time, to reduce the influence of each new sample, since giving new samples a lot of influence makes the Q-updates “forget” the samples further back in time.

def custom_alpha(n_step: int) -> float:

Your custom_alpha must meet these requirements, which the autograder checks (both the local autograder and Gradescope):

• For every n_step from 1 to 10,000, it returns a value greater than 0.0 and at most 1.0.
• custom_alpha(1) >= 0.5 (start with a relatively high learning rate).
• custom_alpha(10000) <= 0.1 (end with a low learning rate).
• It returns at least 10 different values for n_step from 1 to 1,000.

To activate your custom alpha schedule, set solver.use_custom_alpha = True and solver.alpha = None on a QLearningSolver instance. You can test your implementation with

python autograder.py -q q8

As in Q6, the autograder will then run 10,000 Q-learning steps (with ε = 0.2) using your custom alpha schedule.

Note: Our reference solution takes 1 line.

Q9: Report (40 points)

The starter code includes a file a5_report.txt that serves as your report for this assignment (see also the Assignment Reports page). Fill in all parts of the template and submit it to Gradescope along with solver_utils.py. Name the file a5_report_firstname_lastname.txt (using the submitting partner's name). If you are working in a partnership, include both partners' names and IDs in the header.

The template has four parts plus a partnership retrospective:

• Part A — Process (required; no points of its own, but points may be deducted if it is missing): Goals and Activities — a brief narrative of what you set out to do and how your work unfolded.
• Part B — Report Questions (40 points, graded): The six questions below. Questions 3 and 5 require you to run experiments and report numerical results; a short table is expected. Keep answers for the other questions to 3–4 sentences.
• Partnership Retrospective (required; between Parts B and C): This starts with whether or not you worked in a partnership. Then, if so, it will contain (a) the names of the people in your team, (b) how you divided up the work, and (c) what if anything in this collaboration was a new experience for either partner. Students working alone just answer NO. Points may be deducted if the retrospective is missing, especially if you worked in a partnership.
• Part C — Reflection (required; no points of its own, but points may be deducted if it is missing): Challenges & Solutions, Reflections/Learnings, and Next Steps.
• Part D — For the Record (required; no points of its own, but points may be deducted if it is missing): The model(s) and tools you used for agentic programming, and your AI prompting log: the full conversation if it is not longer than 50K bytes, otherwise just your own prompts (up to 100K bytes in total). Question 6 in Part B is your reflective summary; Part D is the supporting record.

Part B questions (40 points total):

1. In the context of the Towers-of-Hanoi World MDP, explain how the Value Iteration algorithm uses the Bellman equations to iteratively compute the value table. (5 points)
2. How did you decide on your custom epsilon function? What thoughts went into that and what would you change to further optimize your exploration? If your function was strong, explain why. (5 points)
3. Run Q-learning with three different exploration strategies: constant ε = 0.2, your custom epsilon schedule, and your exploration function. Use the 3-disk MDP with 20% noise, training for 10,000 steps in each case. Choose three states on or near the solution path, report the learned values for each strategy in a table, and explain any discrepancies you observe. (10 points)
4. For what value of the discount factor γ does Value Iteration fail to find a policy that reaches the goal? Explain why. Consider all the settings available in the GUI, including two goals and the living-reward options. (5 points)
5. Explain how your custom alpha function works and whether it is effective in gradually lowering the learning rate without lowering it too much. Compare Q-learning results with and without your custom alpha after 10,000 training steps, using your Value Iteration results as a benchmark. (10 points)
6. What parts of this assignment did you use AI assistance for? What did the AI get wrong, or what did you have to verify, correct, or rethink? (5 points)

Turn in the following two files to Gradescope, in the assignment “A5”:

solver_utils.py
a5_report_firstname_lastname.txt

Before submitting, you can run the entire local test suite with

python autograder.py

Partnerships. If you are in a partnership, do the following: (1) fill in the partnership comment at the top of solver_utils.py (it is already in the starter code), in this form:

# Partnership? YES
# Submitting partner: John Doe
# Other partner: Jane Smith

(2) when you submit to Gradescope, indicate that this is a group submission and add your partner, and (3) complete the partnership retrospective in your report. If you are working alone, write NO after Partnership?, and answer NO in the retrospective.