I'm trying to reproduce an example from a book by Richard Sutton on Reinforcement Learning (in Chapter 6 of this PDF). Here is the problem statement:

enter image description here

enter image description here

The example discusses the difference between Monte Carlo (MC) and Temporal Difference (TD) learning, but I'd just like to implement TD learning so that it converges.

Following my understanding of the book and http://www.scholarpedia.org/article/Temporal_difference_learning, I tried to reproduce this example with the following Python code:

import numpy as np
np.set_printoptions(precision=3, suppress=True)

class Chain:
    gamma = 1       # Discount factor for future rewards (=1 because the game is finite and deterministic)

    def __init__(self, alpha = 0.1, values = np.ones(7)*0.5):
        self.nodes = ["Left", "A", "B", "C", "D", "E", "Right"]
        self.position = 3       # Initial position is "C"
        self.node = self.nodes[self.position]
        self.values = values
        self.terminated = False
        self.alpha = alpha

    def move(self):
        if not self.terminated:
            direction = np.random.choice(["left", "right"])

            if direction == "left":
                print "Moving to the left."
                new_position = self.position - 1
            elif direction == "right":
                print "Moving to the right."
                new_position = self.position + 1

            reward = self.get_reward(new_position)

            # self.update_value_table_immediate_reward(self.position, new_position)
            self.update_value_table_future_reward(self.position, new_position)

            self.position = new_position
            self.node = self.nodes[self.position]

            if (self.node == "Left") or (self.node == "Right"):
                print "The random walk has terminated."
                self.terminated = True

            print "Moving is not possible as the random walk has already terminated."

    def get_reward(self, new_position):
        return 1.0 if self.nodes[new_position] == "Right" else 0.0

    def update_value_table_immediate_reward(self, old_position, new_position):
        reward = self.get_reward(new_position)
        self.values[old_position] += self.alpha * (reward - self.values[old_position])

    def update_value_table_future_reward(self, old_position, new_position):
        reward = self.get_reward(new_position) + self.gamma * self.values[new_position]
        self.values[old_position] += self.alpha * (reward - self.values[old_position])

value_estimates = np.ones(7) * 0.5      # Initialize estimates at all 0.5

N_episodes = 1000

for episode in range(N_episodes):
    c = Chain(values = value_estimates)         # Use value estimates from previous iteration
    while not c.terminated:
    value_estimates = c.values                  # Update value estimates


If I run the code as it is, I would expect it to at the end print the following array:

[ 0.1667,  0.3333,  0.5   ,  0.6667,  0.8333]

with some slight fluctuations about the expected values. However, instead I get this:

[ 0.691  0.858  1.044  1.214  1.345]

In short, the output of values is not converging to the expected future reward in each state.

If I replace the line with update_value_table_future_reward with update_value_table_immediate_reward in the Chain class, I get the following output:

[ 0.     0.     0.     0.     0.559]

This is more-or-less what I would expect: the expected immediate reward in state "E" is 0.5, and zero in the other states.

What I thus suspect is that there is something wrong with the update_value_table_future_reward function, but I can't see what. Following the Scholarpedia article, I'm trying to implement

$p_t := p_t + \alpha\left[y_{t+1} + \gamma P_t\left(x_{t+1}\right) - p_t \right],$

where the $:=$ denotes the updating at each time step, $p$ is the look-up table values, alpha is the learning rate (set to 0.1 as in the book), gamma is the discount factor for future rewards (set to 1 in this deterministic and finite example), $y_{t+1}$ is the immediate reward received after the move, and $P_t\left(x_{t+1}\right)$ is the expected reward in the next state (the state moved to) using the current value table.

Any ideas on how to implement TD learning for this example?


I think you're double-counting on the update_value_table_future_reward function when you reach a terminal state.

def update_value_table_future_reward(self, old_position, new_position):
    if self.nodes[new_position] in ("Left","Right"):
        reward = self.get_reward(new_position)
        reward = self.get_reward(new_position) + self.gamma * self.values[new_position]
    self.values[old_position] += self.alpha * (reward - self.values[old_position])

After 5,000 episodes, I get the below values:

[ 0.163 0.357 0.557 0.67 0.852]


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.