- Kaden Hart
- Ben Tomlinson
- Python 3.X
- Numpy package
- Matplotlib package
Note: it takes a while to run Also, whenever a graph appears, you have to close it for it to continue to the next. ''' python do_all.py'''
- Epsilon of 0.4 converges the fastest but with the worst average reward of about 7
- Epsilon of 0.1 converges second fastest but not quite with the highest reward, it stabilizes at around 11 Average reward
- Epsilon of 0.05 converges third fastest but at the highest average reward of around 13
- Epsilon of 0.01 converges slowly but eventually surpasses all but e=0.05
Overall e=0.05 seems optimal, it converges slightly slower than e=0.1 but gets a much higher reward than all others, if quick convergence is valued more, then e=0.1 would be optimal.
When using Linear, Asymptoic, and Heavy Asymptotic Quenching:
- Linear has by far the lowest average reward during the 10000 timesteps, and never converges
- Asymptotic has the highest average reward and fastest convergence, just slightly better in both regards than Heavy Asymptotic
- Heavy Asymptotic has the second highest average reward and second fastest convergence, only beaten by a small margin by normal Asymptotic Quenching. It appears that maybe eventually it could crawl above Normal Asymptotic in reward, but it did not within the first 10000 steps
When using Exclude Best and Weighted Exploration:
- Weighted exploration always beat exclude best except for e=0.4 which was by far the worst epsilon value.
- Convergence rate seemed for the most part only dependent on the epsilon value, and not on the exploration method
- For e=0.1, the differences were really small
- Weighing the choices seems to make a difference because rather than potentially picking a really bad option, it picks options that seem to be pretty good. This could cause the algorithm to ignore some good choices if unlucky, but it seems to work well overall!
From these results, we see that Thompson sampling performs much better than the epsilon-greedy-method, especially when it is reset and has a chance to re-evaluate the probabilities on which treatments are best. As the textbook "Algorithms to Live By" puts it,
"The advantage of Thompson Sampling over other algorithms for solving multi-armedbandit problems is its flexibility. Even if the assumptions of the problem change—you have information suggesting one option is better than the others, options depend on one another, options change over time—Thompson’s strategy of pursuing options with a probability that reflects your sense that they are the best currently available still works. So rather than having to derive a new algorithm in each of these cases, we can simply apply Bayes’s Rule and use the results.
I believe that from these results, it can be concluded that randomness helps convergence to an extent. Under changing conditions, randomness is entirely necessary to explore new paths to ensure that the one that is being followed is not a rut. On the other hand, like in the case where epsilon = 0.4, too much randomness can result in aimless wandering, making it impossible to focus on the best option because it will likely be abandoned due to random chance.A small, fixed epsilon value in a dynamic environmant can also lead to missed opportunities for exploration; we see a hint of this in the graph above, where the trend of epsilon = 0.01 drops off compared to the other values under a sudden change.
By modifying ε or using other heuristics, an algorithm can better balance exploration and exploitation as the algorithm learns about the environment. For this reason,a modified version of the epsilon-greedy approach can offer greater adaptability.