Chapter06 Temporal-Difference Learning (Cliff Walking)

6.0 μs

xxxxxxxxxx
 
begin
    using ReinforcementLearning
    using Plots
    using Flux
    using Statistics
end

52.8 s

In Example 6.6, a gridworld example of Cliff Walking is introduced to compare the difference between on-policy (SARSA) and off-policy (Q-learning). Although there's a package of GridWorlds.jl dedicated to 2-D environments, we decide to write an independent implementation here as a showcase.

7.4 μs

4×12 LinearIndices{2,Tuple{Base.OneTo{Int64},Base.OneTo{Int64}}}:
 1  5   9  13  17  21  25  29  33  37  41  45
 2  6  10  14  18  22  26  30  34  38  42  46
 3  7  11  15  19  23  27  31  35  39  43  47
 4  8  12  16  20  24  28  32  36  40  44  48

xxxxxxxxxx
 
begin
    const NX = 4
    const NY = 12
    const Start = CartesianIndex(4, 1)
    const Goal = CartesianIndex(4, 12)
    const LRUD = [
        CartesianIndex(0, -1),  # left
        CartesianIndex(0, 1),   # right
        CartesianIndex(-1, 0),  # up
        CartesianIndex(1, 0),   # down
    ]
    const LinearInds = LinearIndices((NX, NY))
end

57.2 ms

iscliff (generic function with 1 method)

xxxxxxxxxx
 
function iscliff(p::CartesianIndex{2})
    x, y = Tuple(p)
    x == 4 && y > 1 && y < NY
end

39.5 μs

xxxxxxxxxx
 
# take a look at the wordmap
heatmap((!iscliff).(CartesianIndices((NX, NY))); yflip = true)

18.6 s

CliffWalkingEnv

xxxxxxxxxx
 
Base.@kwdef mutable struct CliffWalkingEnv <: AbstractEnv
    position::CartesianIndex{2} = Start
end

6.0 ms

xxxxxxxxxx
 
function (env::CliffWalkingEnv)(a::Int)
    x, y = Tuple(env.position + LRUD[a])
    env.position = CartesianIndex(min(max(x, 1), NX), min(max(y, 1), NY))
end

157 μs

xxxxxxxxxx
 
RLBase.state(env::CliffWalkingEnv) = LinearInds[env.position]

26.3 μs

xxxxxxxxxx
 
RLBase.state_space(env::CliffWalkingEnv) = Base.OneTo(length(LinearInds))

19.4 μs

xxxxxxxxxx
 
RLBase.action_space(env::CliffWalkingEnv) = Base.OneTo(length(LRUD))

31.0 μs

xxxxxxxxxx
 
RLBase.reward(env::CliffWalkingEnv) = env.position == Goal ? 0.0 : (iscliff(env.position) ? -100.0 : -1.0)

20.8 μs

xxxxxxxxxx
 
RLBase.is_terminated(env::CliffWalkingEnv) = env.position == Goal || iscliff(env.position)

19.4 μs

xxxxxxxxxx
 
RLBase.reset!(env::CliffWalkingEnv) = env.position = Start

41.7 μs

world

# CliffWalkingEnv

## 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

`Base.OneTo(48)`

## Action Space

`Base.OneTo(4)`

## Current State

```
4
```

xxxxxxxxxx
 
world = CliffWalkingEnv()

2.5 ms

Now we have a workable environment. Next we create several factories to generate different policies for comparison.

3.0 μs

xxxxxxxxxx
 
begin
    NS = length(state_space(world))
    NA = length(action_space(world))
end

66.0 ns

create_agent (generic function with 1 method)

xxxxxxxxxx
 
create_agent(α, method) = Agent(
    policy = QBasedPolicy(
        learner=TDLearner(
            approximator=TabularQApproximator(
                ;n_state=NS,
                n_action=NA,
                opt=Descent(α),
            ),
            method=method,
            γ=1.0,
            n=0
        ),
        explorer=EpsilonGreedyExplorer(0.1)
    ),
    trajectory=VectorSARTTrajectory()   
)

59.1 μs

repeated_run (generic function with 2 methods)

xxxxxxxxxx
 
function repeated_run(α, method, N, n_episode, is_mean=true)
    env = CliffWalkingEnv()
    rewards = []
    for _ in 1:N
        h = TotalRewardPerEpisode()
        run(
            create_agent(α, method),
            env, 
            StopAfterEpisode(n_episode;is_show_progress=false),
            h
        )
        push!(rewards, is_mean ? mean(h.rewards) : h.rewards)
    end
    mean(rewards)
end

43.8 μs

xxxxxxxxxx
 
begin
    p = plot(legend=:bottomright)
    plot!(p, repeated_run(0.5, :SARS, 1000, 500, false), label="QLearning")
    plot!(p, repeated_run(0.5, :SARSA, 1000, 500, false), label="SARSA")
    p
end

118 s

xxxxxxxxxx
 
begin
    A = 0.1:0.05:0.95
    fig_6_3 = plot(;legend=:bottomright)
​
    plot!(fig_6_3, A, [repeated_run(α, :SARS, 100, 100) for α in A], linestyle=:dash ,markershape=:rect, label="Interim Q")
    plot!(fig_6_3, A, [repeated_run(α, :SARSA, 100, 100) for α in A], linestyle=:dash, markershape=:dtriangle, label="Interim SARSA")
    plot!(fig_6_3, A, [repeated_run(α, :ExpectedSARSA, 100, 100) for α in A], linestyle=:dash, markershape=:cross, label="Interim ExpectedSARSA")
​
    plot!(fig_6_3, A, [repeated_run(α, :SARS, 10, 5000) for α in A], linestyle=:solid ,markershape=:rect, label="Asymptotic interim Q")
    plot!(fig_6_3, A, [repeated_run(α, :SARSA, 10, 5000) for α in A], linestyle=:solid, markershape=:dtriangle, label="Asymptotic SARSA")
    plot!(fig_6_3, A, [repeated_run(α, :ExpectedSARSA, 10, 5000) for α in A], linestyle=:solid, markershape=:cross, label="Asymptotic ExpectedSARSA")
    fig_6_3
end

384 s