RL ⇨ Tabular Learning Algorithms

My implementation of chapers 2-8 in Richard Sutton & Andrew Barto's book An Introduction to Reinforcement Learning.

GitHub Repo

  • A k-armed Bandit Problem
    Action-value Methods
    The 10-armed Testbed
    Incremental Implementation
    Tracking a Nonstationary Problem
    Optimistic Initial Values
    Upper-Confidence-Bound Action Selection
    Gradient Bandit Algorithms
    Associative Search (ContextualBandits)
    • Chapter description...

    A k-armed Bandit Problem
    Action-value Methods
    The 10-armed Testbed

    Histograms of my 7 bandits.

    Violin plots of my 7 bandits.

    ε-greedy action-value methods on the 10-armed testbed.

    Incremental Implementation
    Tracking a Nonstationary Problem
    Optimistic Initial Values

    Optimistic initial action-value estimates on the 10-armed testbed, and on my distributions on the right. Step-size: α = 0.1.

    Upper-Confidence-Bound Action Selection

    UCB action selection on the 10-armed testbed.
    Gradient Bandit Algorithms

    Gradient bandit algorithm with and without a reward baseline on the 10-armed testbed.
    Associative Search (ContextualBandits)

    Parameter sweep of bandit algorithms, on the 10-armed testbed and my pdfs on the left.

    Random.

    ε-Greedy.

    Softmax.

    Decaying ε-Greedy.

    Gradient.

    UCB.

    Proportion of times the optimal actions vs iterations for different action selection methods on my bandits.

  • The Agent–Environment Interface
    Goals and Rewards
    Returns and Episodes
    Unified Notation for Episodic and Continuing Tasks
    Policies and Value Functions
    Optimal Policies and Optimal Value Functions
    Optimality and Approximation
    Policy Evaluation (Prediction)
    Policy Improvement
    Policy Iteration
    Value Iteration
    Asynchronous Dynamic Programming
    Generalized Policy Iteration
    Efficiency of Dynamic Programming
    • Chapter description...

    The Agent–Environment Interface
    Goals and Rewards
    Returns and Episodes
    Unified Notation for Episodic and Continuing Tasks
    Policies and Value Functions

    Learning gvalue function and greedy policy on my gridworld.

    Gridworld example: A->A' +10, B->B' +5; Value function for the equiprobable random policy.
    Optimal Policies and Optimal Value Functions

    Optimal solutions to the gridworld example.
    Optimality and Approximation
    Policy Evaluation (Prediction)
    Policy Improvement

    V and π after iterative policy evaluation on a small gridworld.
    Policy Iteration
    Value Iteration

    Gambler’s problem with ph = 0.4. Left: Value function found by successive sweeps of value iteration. Right: Final policy.

    Asynchronous Dynamic Programming
    Generalized Policy Iteration
    Efficiency of Dynamic Programming

  • Monte Carlo Prediction
    Monte Carlo Estimation of Action Values
    Monte Carlo Control
    Monte Carlo Control without Exploring Starts
    Off-policy Prediction via Importance Sampling
    Incremental Implementation
    Off-policy Monte Carlo Control
    Discounting-aware Importance Sampling
    Per-decision Importance Sampling
    • Chapter description...

    Monte Carlo Prediction
    Monte Carlo Estimation of Action Values
    Monte Carlo Control
    Monte Carlo Control without Exploring Starts
    Off-policy Prediction via Importance Sampling

    Ordinary importance sampling produces unstable estimates on a simple one-state MDP.
    Incremental Implementation
    Off-policy Monte Carlo Control
    Discounting-aware Importance Sampling
    Per-decision Importance Sampling

    Monte Carlo.

    Off-Policy MC.

    ε-soft MC.

  • TD Prediction
    Advantages of TD Prediction Methods
    Optimality of TD(0)
    Sarsa: On-policy TD Control
    Q-learning: Off-policy TD Control
    Expected Sarsa
    Maximization Bias and Double Learning
    Games, Afterstates, and Other Special Cases
    • Chapter description...

    TD Prediction
    Advantages of TD Prediction Methods

    Left: values learned after various numbers of episodes on a single run of TD(0). Right: learning curves for the two methods for various values of α

    Optimality of TD(0)

    TD(0) and constant-α MC with batch training on the random walk task.
    Sarsa: On-policy TD Control
    Q-learning: Off-policy TD Control
    Expected Sarsa

    Sarsa on my grid-world.

    Maximization Bias and Double Learning

    Q-learning and Double Q-learning on a simple episodic MDP, Double Q-learning is almost unaffected by maximization bias..
    Games, Afterstates, and Other Special Cases

  • n-step TD Prediction
    n-step Sarsa
    n-step Off-policy Learning
    Per-decision Methods with Control Variates
    Off-policy Learning Without Importance Sampling: The n-step Tree Backup Algorithm
    A Unifying Algorithm: n-step Q(σ)
    • Chapter description...

    n-step TD Prediction

    n-step TD as a function of α, for varying values of n, on a 19-state random walk task.
    n-step Sarsa

    n-Step Bootstrapping TD algorithms on my gridworld problem.

    n-step Off-policy Learning
    Per-decision Methods with Control Variates
    Off-policy Learning Without Importance Sampling: The n-step Tree Backup Algorithm
    A Unifying Algorithm: n-step Q(σ)