mountain car pomcp oscillating solution

[gdaddi]

Hi,
I tried solving the mountain car example domain using pomcp, but the resulting behavior is unexpected.
The image shows position over time steps, and even though the policy is always returning action 1.0, state oscillates like this.

Does anyone know what I am doing wrong? I would expect an always 1.0 action to send the car towards higher x. Thanks.

Code is this:

import QuickPOMDPs: QuickPOMDP
  import POMDPTools: ImplicitDistribution
  import Distributions: Normal
  using BasicPOMCP, POMDPSimulators
  using POMDPs
 using POMDPModels
 using ParticleFilters, Distributions
 using Plots

  
mountaincar = QuickPOMDP(
    actions = [-1., 0., 1.],
    obstype = Float64,
    discount = 0.95,

    transition = function (s, a)        
        ImplicitDistribution() do rng
            x, v = s
            vp = v + a*0.001 + cos(3*x)*-0.0025 + 0.0002*randn(rng)
            vp = clamp(vp, -0.07, 0.07)
            xp = x + vp
            return (xp, vp)
        end
    end,

    observation = (a, sp) -> Normal(sp[1], 0.15),

    reward = function (s, a, sp)
        if sp[1] > 0.5
            return 100.0
        else
            return -1.0
        end
    end,

    initialstate = ImplicitDistribution(rng -> (-0.2*rand(rng), 0.0)),
    isterminal = s -> s[1] > 0.5
  )

solver = POMCPSolver()
planner = solve(solver, mountaincar)
# policy = solve(solver, mountaincar)
up = BootstrapFilter(mountaincar, 100)


s_hist = []
a_hist = []
o_hist = []
for (s, a, o) in stepthrough(mountaincar, planner, up, "s,a,o", max_steps=1000)
    println("State was $s,")
    println("action $a was taken,")
    println("and observation $o was received.\n")
    push!(s_hist, s[1]) # save position
    push!(a_hist, a)
    push!(o_hist, o)
end

display(plot(s_hist, label="state"))

Some terminal outputs:

State was (-0.011463162602614528, 0.0111420154077664),
action 1.0 was taken,
and observation 0.039084613845056446 was received.

State was (-0.001891143006727698, 0.00957201959588683),
action 1.0 was taken,
and observation -0.1931042689496777 was received.

State was (0.006298863159559274, 0.008190006166286972),
action 1.0 was taken,
and observation -0.005753845171385099 was received.

State was (0.012798821236518135, 0.006499958076958861),
action 1.0 was taken,
and observation -0.1503518515176861 was received.

[zsunberg]

Hi @gdaddi,

The problem is likely that POMCP is just not able to solve this problem very well without a decent rollout policy.

Since the rewards for the problem are very sparse, the tree search likely never finds any rewards in the tree if the rollout policy is random. You could try to use a rollout policy that always adds energy so that the rollouts will reach the goal.

Let me know if this explanation makes sense.

[zsunberg]

nice! that is a pretty decent way to do it. However, it is tricky to determine whether your heuristic value function estimate is actually a good estimate of the value throughout the state space. Another way would be to actually run the rollouts with an energy-increasing policy - something like:

energy(s) = sign(s[2])
POMCPSolver(estimate_value = FORollout(FunctionPolicy(energy)))

That will ensure that the value matches the reward function.

[gdaddi]

Thank you again.

I tried the rollout policy above, but it chooses always 1.0 as next action action. Resulting once again in this oscillating behavior. I was thinking that maybe the rollout policy does not simulate enough steps to reach any reward - even with the correct policy. Is there a way to set rollout length?
.

I also tried creating a FunctionPolicy to apply as a baseline policy: "always add energy looking at velocity belief".

function energy_function(b)
    v_mean = 0
    for particle in particles(b)
        v_mean += particle[2]
    end
    v_mean /= n_particles(b)
    println(v_mean)
    if v_mean > 0
        return 1.
    else
        return -1.
    end
end
planner2 = FunctionPolicy(energy_function)

Unfortunately, that is also giving strange results. The solution diverges toward negative values. Do you think this is a problem in the domain?

[zsunberg]

was thinking that maybe the rollout policy does not simulate enough steps to reach any reward - even with the correct policy. Is there a way to set rollout length?

Yes, this is a likely culprit - I think the rollouts obey the max_depth keyword argument, so perhaps set that to 100

Unfortunately, that is also giving strange results. The solution diverges toward negative values. Do you think this is a problem in the domain?

Well, it looks like it just goes over the hill to the left in the negative direction and keeps going. Maybe you should adjust the energy policy so that if it gets to far to the left (negative position), it takes action +1.

Also, it should be noted that POMCP will not work very well for this problem in many cases because of the reasons described here: https://arxiv.org/abs/1709.06196

[gdaddi]

Awesome, thanks! Both solutions work splendidly.

I was wondering what your take on solving this problem offline is (in particular, I have been trying to get MCVI working with this domain). Do you think it is a waste of time?

[zsunberg]

MCVI might work, just be sure you are using the observation classifier version that can handle continuous observations (which I think is the default in the MCVI.jl package).

In reality this is not a difficult POMDP because the belief will be unimodal. In general if your beliefs are unimodal and the reward function is nicely behaved it is sufficient to calculate the mean state of the belief and use a policy for the underlying fully observable MDP to solve the POMDP. This is called "certainty-equivalent" control. In fact, in the linear-quadratic-gaussian case, certainty equivalent control is optimal.

To solve this offline, I would recommend solving the MDP version somehow and then using a Kalman (since the dynamics are nearly linear) or particle filter to estimate the mean of the belief and using certainty-equivalent control.