Project · 21 steps · Medium
Bandits and Dynamic Programming from Scratch
Implement core multi-armed bandit algorithms and dynamic-programming methods. Build stationary and nonstationary bandit testbeds, compare epsilon-greedy, optimistic, UCB and gradient strategies, then solve gridworld and gambler MDPs with policy and value iteration.
Each step is one function with tests. Your code runs in the browser, and every step builds on the ones before it.
Part 1: Stationary k-Armed Bandits
Build a seeded bandit testbed, implement incremental sample-average updates and epsilon-greedy selection, then average reward and optimal-action curves over many runs.
create_bandit_testbedpull_armsample_average_updateepsilon_greedy_actionrun_bandit_episodetrack_rewards_and_optimal_actionsaverage_bandit_curves
Part 2: Nonstationary and Advanced Bandits
Add random-walk nonstationarity, constant step-size updates, optimistic initialization, UCB action selection and gradient bandits, then run a parameter study comparing all methods.
apply_random_walk_driftconstant_step_size_updateoptimistic_initializationucb_action_selectgradient_bandit_updatebandit_parameter_study
Part 3: Gridworld Dynamic Programming
Encode the book gridworld as an MDP, perform iterative policy evaluation and greedy improvement, run full policy iteration, and solve the same MDP directly with value iteration.
build_gridworld_mdpiterative_policy_evaluationgreedy_policy_improvementpolicy_iterationvalue_iteration
Part 4: Gambler's Problem
Model the capital-betting MDP, compute optimal state values with value iteration, and extract the optimal stake for every capital level.
build_gambler_mdpgambler_value_iterationextract_optimal_stakes