Chapter 10 Mountain Car

6.3 μs

xxxxxxxxxx
 
begin
    using ReinforcementLearning
    using Flux
    using Statistics
    using Plots
    using SparseArrays
end

66.3 s

The MountainCarEnv is already provided in ReinforcementLearning.jl. So we can use it directly here. Note that by default this environment will terminate at the maximum step of 200. While in the example on the book there's no such restriction.

5.1 μs

env

# MountainCarEnv

## Traits

| Trait Type        |                                            Value |
|:----------------- | ------------------------------------------------:|
| NumAgentStyle     |          ReinforcementLearningBase.SingleAgent() |
| DynamicStyle      |           ReinforcementLearningBase.Sequential() |
| InformationStyle  | ReinforcementLearningBase.ImperfectInformation() |
| ChanceStyle       |           ReinforcementLearningBase.Stochastic() |
| RewardStyle       |           ReinforcementLearningBase.StepReward() |
| UtilityStyle      |           ReinforcementLearningBase.GeneralSum() |
| ActionStyle       |     ReinforcementLearningBase.MinimalActionSet() |
| StateStyle        |     ReinforcementLearningBase.Observation{Any}() |
| DefaultStateStyle |     ReinforcementLearningBase.Observation{Any}() |

## Is Environment Terminated?

No

## State Space

`ReinforcementLearningBase.Space{Array{IntervalSets.Interval{:closed,:closed,Float64},1}}(IntervalSets.Interval{:closed,:closed,Float64}[-1.2..0.6, -0.07..0.07])`

## Action Space

`Base.OneTo(3)`

## Current State

```
[-0.5834095103051787, 0.0]
```

xxxxxxxxxx
 
env = MountainCarEnv()

569 ms

Space{Array{IntervalSets.Interval{:closed,:closed,Float64},1}}sIntervalSets.Interval{:closed,:closed,Float64}1

-1.2..0.6

-0.07..0.07

xxxxxxxxxx
 
S = state_space(env)

279 ns

First let's define a Tiling structure to encode the state.

3.5 μs

encode (generic function with 2 methods)

xxxxxxxxxx
 
begin
    struct Tiling{N,Tr<:AbstractRange}
        ranges::NTuple{N,Tr}
        inds::LinearIndices{N,NTuple{N,Base.OneTo{Int}}}
    end
​
    Tiling(ranges::AbstractRange...) =Tiling(
        ranges,
        LinearIndices(Tuple(length(r) - 1 for r in ranges))
    )
​
    Base.length(t::Tiling) = reduce(*, (length(r) - 1 for r in t.ranges))
​
    function Base.:-(t::Tiling, xs)
        Tiling((r .- x for (r, x) in zip(t.ranges, xs))...)
    end
​
    encode(range::AbstractRange, x) = floor(Int, div(x - range[1], step(range)) + 1)
​
    encode(t::Tiling, xs) = t.inds[CartesianIndex(Tuple(map(encode,  t.ranges, xs)))]
end

20.3 ms

Main.workspace57.Tiling{2,StepRangeLen{Float64,Base.TwicePrecision{Float64},Base.TwicePrecision{Float64}}}1Tiling{2,StepRangeLen{Float64,TwicePrecision{Float64},TwicePrecision{Float64}}}ranges1

-1.2:0.22499999999999998:0.825

-0.07:0.0175:0.0875

inds

9×9 LinearIndices{2,Tuple{OneTo{Int64},OneTo{Int64}}}:
 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81

2Tiling{2,StepRangeLen{Float64,TwicePrecision{Float64},TwicePrecision{Float64}}}ranges1

-1.228125:0.22499999999999998:0.796875

-0.0721875:0.0175:0.0853125

inds

9×9 LinearIndices{2,Tuple{OneTo{Int64},OneTo{Int64}}}:
 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81

3Tiling{2,StepRangeLen{Float64,TwicePrecision{Float64},TwicePrecision{Float64}}}ranges1

-1.2562499999999999:0.22499999999999998:0.7687499999999999

-0.074375:0.0175:0.083125

inds

9×9 LinearIndices{2,Tuple{OneTo{Int64},OneTo{Int64}}}:
 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81

4Tiling{2,StepRangeLen{Float64,TwicePrecision{Float64},TwicePrecision{Float64}}}ranges1

-1.284375:0.22499999999999998:0.740625

-0.0765625:0.0175:0.0809375

inds

9×9 LinearIndices{2,Tuple{OneTo{Int64},OneTo{Int64}}}:
 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81

5Tiling{2,StepRangeLen{Float64,TwicePrecision{Float64},TwicePrecision{Float64}}}ranges1

-1.3125:0.22499999999999998:0.7124999999999999

-0.07875:0.0175:0.07875

inds

9×9 LinearIndices{2,Tuple{OneTo{Int64},OneTo{Int64}}}:
 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81

6Tiling{2,StepRangeLen{Float64,TwicePrecision{Float64},TwicePrecision{Float64}}}ranges1

-1.340625:0.22499999999999998:0.684375

-0.0809375:0.0175:0.0765625

inds

9×9 LinearIndices{2,Tuple{OneTo{Int64},OneTo{Int64}}}:
 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81

7Tiling{2,StepRangeLen{Float64,TwicePrecision{Float64},TwicePrecision{Float64}}}ranges1

-1.36875:0.22499999999999998:0.65625

-0.083125:0.0175:0.074375

inds

9×9 LinearIndices{2,Tuple{OneTo{Int64},OneTo{Int64}}}:
 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81

8Tiling{2,StepRangeLen{Float64,TwicePrecision{Float64},TwicePrecision{Float64}}}ranges1

-1.3968749999999999:0.22499999999999998:0.628125

-0.0853125:0.0175:0.0721875

inds

9×9 LinearIndices{2,Tuple{OneTo{Int64},OneTo{Int64}}}:
 1  10  19  28  37  46  55  64  73
 2  11  20  29  38  47  56  65  74
 3  12  21  30  39  48  57  66  75
 4  13  22  31  40  49  58  67  76
 5  14  23  32  41  50  59  68  77
 6  15  24  33  42  51  60  69  78
 7  16  25  34  43  52  61  70  79
 8  17  26  35  44  53  62  71  80
 9  18  27  36  45  54  63  72  81

xxxxxxxxxx
 
begin
    ntilings = 8
    ntiles = 8
    tiling = Tiling(
        (
            range(r.left, step=(r.right-r.left)/ntiles, length=ntiles+2)
            for r in S
        )...
    )
    offset = map(x-> x.right - x.left, S) ./ (ntiles * ntilings)
    tilings = [tiling - offset .* (i-1) for i in 1:ntilings]
end

388 ms

The rest parts are simple, we initialize agent and env, then roll out experiments:

3.5 μs

create_env_agent (generic function with 3 methods)

xxxxxxxxxx
 
function create_env_agent(α=2e-4, n=0)
    env = StateOverriddenEnv(
        MountainCarEnv(;max_steps=10000),
        s -> sparse(map(t -> encode(t, s), tilings), 1:8, ones(8), 81, 8) |> vec
    )
​
    agent = Agent(
        policy=QBasedPolicy(
            learner=TDLearner(
                approximator=LinearQApproximator(
                    n_state=81*8,
                    n_action=3,
                    opt = Descent(α)
                    ),
                method=:SARSA,
                n=n
                ),
            explorer=GreedyExplorer()
            ),
        trajectory=VectorSARTTrajectory(;state=Vector{Int})
    )
​
    env, agent
end

131 μs

-1.2:0.046153846153846156:0.6

xxxxxxxxxx
 
X = range(S[1].left, stop=S[1].right, length=40)

243 ms

-0.07:0.0035897435897435897:0.07

xxxxxxxxxx
 
Y = range(S[2].left, stop=S[2].right, length=40)

9.0 μs

show_approximation (generic function with 1 method)

xxxxxxxxxx
 
function show_approximation(n)
    env, agent = create_env_agent()
    run(agent, env, StopAfterEpisode(n))
    [
        agent.policy.learner.approximator(env.f([p, v])) |> maximum
        for p in X, v in Y
    ]
end

69.5 μs

xxxxxxxxxx
 
n = 10

84.0 ns

xxxxxxxxxx
 
plot(X, Y, -show_approximation(n), linetype=:wireframe)

25.4 s

xxxxxxxxxx
 
begin
    fig_10_2 = plot(legend=:topright)
    n_runs = 5  # quite slow here, need revisit
    for α in [0.1/8, 0.2/8, 0.5/8]
        avg_steps_per_episode = zeros(500)
        for _ in 1:n_runs
            env, agent = create_env_agent(α)
            hook = StepsPerEpisode()
            run(agent, env, StopAfterEpisode(500; is_show_progress=false),hook)
            avg_steps_per_episode .+= hook.steps
        end
        plot!(fig_10_2, avg_steps_per_episode ./ n_runs, yscale=:log10, label="α=$α")
    end
    fig_10_2
end

59.2 s

xxxxxxxxxx
 
begin
    function run_once(α, n;is_reduce=true, n_episode=50)
        env, agent = create_env_agent(α, n)
        hook = StepsPerEpisode()
        run(agent, env, StopAfterEpisode(n_episode; is_show_progress=false),hook)
        is_reduce ? mean(hook.steps) : hook.steps
    end
    fig_10_3 = plot()
    plot!(fig_10_3, mean(run_once(0.5/8, 1; is_reduce=false, n_episode=500) for _ in 1:10), yscale=:log10)
    plot!(fig_10_3, mean(run_once(0.3/8, 8; is_reduce=false, n_episode=500) for _ in 1:10), yscale=:log10)
    fig_10_3
end

57.4 s

xxxxxxxxxx
 
begin
    fig_10_4 = plot(legend=:topright)
    for (A, n) in [(0.4:0.1:1.7, 1), (0.3:0.1:1.6, 2), (0.2:0.1:1.4, 4), (0.2:0.1:0.9, 8), (0.2:0.1:0.7, 16)]
        plot!(fig_10_4, A, [mean(run_once(α/8, n) for _ in 1:5) for α in A], label="n = $n")
    end
    fig_10_4
end

140 s