Experiments with bandit algorithms from the 2nd chapter of Sutton and Barto's Reinforcement Learning: An Introduction.
You can generate each plot with the command written under it.
The experimental setup follows the one described in the book:
The values for each action are drawn from a normal distribution with zero mean and unit variance and do not change during the experiment. The bandits take 1000 steps in the environment choosing from 10 actions at each step. Furthermore, the bandits observe rewards with noise drawn from normal distribution with zero mean and unit variance added to the action values. The experiments are repeated 2000 times.
I plot the average reward and the percentage of times the bandit chose the optimal actions.
I replicated Figure 2.1 from the book to check my implementation. ε-greedy bandit outperforms a greedy bandit in this simple testbed.
python -m scripts.compare_bandits_stationary images/book_1 -a epsilon epsilon epsilon -s 0.0 0.01 0.1 -l "ε=0", "ε=0.01" "ε=0.1" -t "ε-greedy bandits"
Next, I compare ε-greedy bandits with different exploration settings. ε=0.1 performs the best.
python -m scripts.compare_bandits_stationary images/epsilon -a epsilon epsilon epsilon epsilon epsilon epsilon -s 0.0 0.01 0.1 0.2 0.5 1.0 -l "ε=0" "ε=0.01" "ε=0.1" "ε=0.2" "ε=0.5" "ε=1.0" -t "ε-greedy bandits"
Another type of bandit presented in the book is the softmax bandit. Softmax bandits should perform better than ε-greedy bandits because they avoid bad actions during exploration. However, they are quite sensitive to the temperature (τ) parameter setting.
python -m scripts.compare_bandits_stationary images/softmax -a softmax softmax softmax softmax softmax -s 0.1 0.2 0.5 1.0 2.0 -l "τ=0.1" "τ=0.2" "τ=0.5" "τ=1.0" "τ=2.0" -t "softmax bandits"
Optimistic Initialization is an alternative to ε-greedy or softmax exploration policies. It outperforms the ε-greedy bandit in this simple environment but has some drawback (e.g. it cannot track non-stationary rewards). Interestingly, the optimistically initialized bandit chooses the optimal action with lower frequency than the ε-greedy bandit but still achieves higher average reward.
python -m scripts.compare_bandits_stationary images/optimistic_init -a epsilon epsilon -s 0.0 0.1 -i 5.0 0.0 -l "ε=0, init=5" "ε=0.1, init=0" -t "Optimistic Initialization"
Finally, I compare the best ε-greedy, softmax and optimistically initialized bandits. The softmax bandit wins by a small margin.
python -m scripts.compare_bandits_stationary images/epsilon_vs_softmax_vs_optimistic -a epsilon epsilon softmax -s 0.1 0.0 0.2 -l "ε=0.1, init=0", "ε=0, init=5" "τ=0.2, init=0" -i 0.0 5.0 0.0
In this experiment, all action values start at 0. After all agents perform a single action, the action values take a small random step drawn from a normal distribution. Therefore, the action values change as the bandits interact with the environment.
I compare the ε-greedy bandit from the previous section with a modified version that uses a constant α during sample averaging. Constant α value causes it to prioritize recent rewards, which models the non-stationary environment better.
The agents take 5000 steps in the environment instead of 1000, so that we can see the gap between the two agents increase.
python -m scripts.compare_bandits_nonstationary images/nonstationary -a epsilon epsilon -s 0.1 0.1 --alphas 0.0 0.1 -l "α=1/k" "α=0.1" -t "ε-greedy bandits, ε=0.1"
UCB bandits establish an upper bound on regret–how much we loose for not playing the optimal action. UCB1 beats ε-greedy while not having any parameters to tune.
python -m scripts.compare_bandits_stationary images/ucb1 -a ucb1 epsilon -s 0.0 0.1 -l "UCB1" "ε-greedy (ε=0.1)"
UCB2 tightens the bound on the regret but introduces an additional parameter α.
python -m scripts.compare_bandits_stationary images/ucb2_alpha -a ucb2 ucb2 ucb2 ucb2 -s 0.001 0.01 0.1 0.5 -l "α=0.001" "α=0.01" "α=0.1" "α=0.5" -t UCB2
UCB2 reaches optimal performance faster than UCB1..
python -m scripts.compare_bandits_stationary images/ucb2 -a ucb2 ucb1 epsilon -s 0.5 0.0 0.1 -l "UCB2 (α=0.5)" "UCB1" "ε-greedy (ε=0.1)"
Install Python 3 and all packages listed in requirements.txt.
Each scripts contains documentation for all arguments.
For stationary experiments, execute:
python -m scripts.compare_bandits_stationary -h
and for non-stationary experiments:
python -m scripts.compare_bandits_nonstationary -h