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.

  1. create_bandit_testbed
  2. pull_arm
  3. sample_average_update
  4. epsilon_greedy_action
  5. run_bandit_episode
  6. track_rewards_and_optimal_actions
  7. average_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.

  1. apply_random_walk_drift
  2. constant_step_size_update
  3. optimistic_initialization
  4. ucb_action_select
  5. gradient_bandit_update
  6. bandit_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.

  1. build_gridworld_mdp
  2. iterative_policy_evaluation
  3. greedy_policy_improvement
  4. policy_iteration
  5. value_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.

  1. build_gambler_mdp
  2. gambler_value_iteration
  3. extract_optimal_stakes