Editing Reinforcement learning (section)

== Exploration ==
The exploration vs. exploitation trade-off has been most thoroughly studied through the [[multi-armed bandit]] problem and for finite state space Markov decision processes in Burnetas and Katehakis (1997).<ref name="Optimal adaptive policies for Marko">{{citation | last1 = Burnetas|first1 = Apostolos N.|last2 = Katehakis|first2 = Michael N.|author-link2 = Michael N. Katehakis|year = 1997|title = Optimal adaptive policies for Markov Decision Processes|journal = [[Mathematics of Operations Research]] |volume = 22 | issue=1 |pages = 222–255 |doi=10.1287/moor.22.1.222 | jstor=3690147}}</ref>

Reinforcement learning requires clever exploration mechanisms; randomly selecting actions, without reference to an estimated probability distribution, shows poor performance. The case of (small) finite Markov decision processes is relatively well understood. However, due to the lack of algorithms that scale well with the number of states (or scale to problems with infinite state spaces), simple exploration methods are the most practical.

One such method is <math>\varepsilon</math>-greedy, where <math>0 < \varepsilon < 1</math> is a parameter controlling the amount of exploration vs. exploitation. With probability <math>1-\varepsilon</math>, exploitation is chosen, and the agent chooses the action that it believes has the best long-term effect (ties between actions are broken uniformly at random). Alternatively, with probability <math>\varepsilon</math>, exploration is chosen, and the action is chosen uniformly at random. <math>\varepsilon</math> is usually a fixed parameter but can be adjusted either according to a schedule (making the agent explore progressively less), or adaptively based on heuristics.<ref>{{citation | last1 = Tokic | first1 = Michel | last2 = Palm | first2 = Günther | chapter   = Value-Difference Based Exploration: Adaptive Control Between Epsilon-Greedy and Softmax | pages = 335–346 | publisher = Springer | series = Lecture Notes in Computer Science | title = KI 2011: Advances in Artificial Intelligence | volume = 7006 | year = 2011 | chapter-url = http://www.tokic.com/www/tokicm/publikationen/papers/KI2011.pdf | isbn = 978-3-642-24455-1}}</ref>