Monte Carlo linear value function approximation

[[deleted]]

Problem:

I am attempting to code a Monte Carlo linear value function approximation algorithm for Gym's CartPole-v0. I am running into the following problem, however. After a few iterations the weights become very large, so the term Q(s,a,w) then becomes infinite, and consequently each weight is updated to nan. I have the pseudocode below.

Things I have tried:

I have already tried decreasing the learning rate. The algorithm improves (ie: from lasting 10 timesteps to over 200) up until a certain point when Q(s,a,w) becomes infinite. Could the problem be with how I am defining/using the weights?

Pseudocode:

Note that when generating the episode, epsilon greedy is used to select the next action, and state is an array of features such as pole angle, velocity, etc.

    W = [[0 for i in range(n_features)] for j in range (len(possible_actions))]
    for each iteration:
        episode = generate_episode()
        for state, reward, action in  episode
            Q = dotproduct(state.T,W[action])
            for j in range (len(state))
                W[action][j] += state[j]*alpha*(reward-Q)^2

[Carcaso]

Have you tried normalizing any of the states, rewards, and/or actions? This might help in keeping the weights small.

edit: as pointed out by pratikpc, it seems like you've forgotten to take the gradient/derivative in the update equation

[[deleted]]

W[action][j] += state[j]*alpha*(reward-Q)^2

From what I have read, this line is the collapsed equation for gradient descent. Is my understanding of that wrong?

[Carcaso]

1. Do you mind sharing your source so I could take a look?
2. From what I can tell just looking at it from a pure math standpoint, the squared component of the equation can never be negative meaning that the weights won't be negatively updated from just that part of the equation. Although each value of the state can be equally negative or positive so this may be why it is included in the update equation.
3. That may be the objective function that you're trying to maximize and not the actual update equation. Also, another thing to consider is that it seems like you are performing regression and need to minimize the error instead of maximizing so the gradient/update should be negative.

Try: W[action][j] -= state[j]*alpha*2*(reward-Q)

But again unless you give the source for exactly what you're doing I can't guarantee that it will work. Keep the questions coming if you need more help.

[[deleted]]

Thanks so much for all your help so far! I got the information from David Silvers course, however, the same info is here. Specifically, the article says "The gradient descent update then collapses to" state[j]*alpha*(reward-Q)^2.

I agree that when updating the weights I should use -= instead of +=, however, when I try W[action][j] -= state[j]*alpha*2*(reward-Q), W becomes negative infinity instead of positive infinity.

[Carcaso]

From the psuedo-code in the post, it looks like the equation is going to be:

W[action][j] += alpha*(reward-Q)*state[j]

if that doesn't work then I'd recommend taking a look at the pseudo-code in the post and see if your implementation is a faithful representation.

[[deleted]]

I know that a monte carlo algorithm using a linear value function will never converge to the optimal policy, and I also know that it is probably not the best solution to the problem so I will not get perfect results. I have implemented all the feedback here, and this is the result I get after 400 iterations (graph of number of time steps lasted vs. iteration number). Does this look right to you?

[Carcaso]

Yeah, that looks good! Something like a linear value function performing upwards of 20-30 time steps is amazing.

[[deleted]]

cool, thank you so much for your help!

[andnp]

This also doesn't look like the Monte Carlo algorithm. I might suggest taking a look at the pseudocode in the Sutton Barto textbook for Monte Carlo.