The Explore vs. Exploit Dilemma
nathanzhao.cc
The Explore vs. Exploit Dilemma
1–10 of 16 posts
Re: The Explore vs. Exploit Dilemma
#2A wonderful treatise on the same topic, “Reinforcement Learning Bit by Bit”, for anyone looking for a more advanced treatment of explore/exploit.
Re: The Explore vs. Exploit Dilemma
#3See also Thompson sampling[+] for a different approach to multi-armed bandits that doesn't depend on explicitly distinguishing between explore-exploit.
Re: The Explore vs. Exploit Dilemma
#4Thanks for writing, a problem I struggle with. I think confidence in oneself impacts the decision. You seem to be highly employable, meaning you can err on the side of exploration. I’m less convinced about that for myself, which makes me anxious to keep exploring. Although I find it very difficult to resist that part of my nature!
Re: The Explore vs. Exploit Dilemma
#5I've been using evolutionary techniques with Pareto front optimization to deal with this tradeoff. If two (or more) objectives are in direct conflict, but otherwise don't dominate one another, we simply take them all. Then, the problem becomes one of making sure you have enough resources to maintain the frontier across the generations. If you do have to collapse the frontier, you can use things like crowding score to maintain diversity.
Example use case - minimizing total neuron activations in a spiking neural simulation while simultaneously maximizing activation coverage and output correctness scores. You don't necessarily know if the cheaper to simulate, but less correct, candidate represents a better evolutionary path until you go down it a few steps.
This also gives you an idea of what your horizon looks like on the fitness landscape. If your Pareto front is small, you are typically deep into exploitation. A simple forward path. If it is large, you are putting more resources into exploration, but you aren't giving up exploitation - it just takes longer to get through the jungle bits. This can be used as a heuristic to inform restarting or other strategic corrective measures in the evolutionary algorithm. If we are stuck in jungle for too long, we might decide to abandon the run and pick new hyperparameters.
Re: The Explore vs. Exploit Dilemma
#6genuine question (the maths lost me): this seems like a philosophical problem. Did the writing of that dilemma into mathematical language bring any interesting result, compared to using regular english ?
Re: The Explore vs. Exploit Dilemma
#7This is a topic I love to study. The mathematical analysis is reasonable; the policy gradient is a classic approach; I love Sutton’s RL book on it: http://incompleteideas.net/book/RLbook2020.pdf
Even though nowadays many people rather use cross-entropy for training RL, which I believe leads to more stable training.
Some of the equations feel a bit imprecise. I prefer to use random variables (rather than the U term), so that uncertainty permeates every value. As a result, the epsilon-t formula might be a perfectible fit (it goes negative past a certain t, which is unrealistic).
Re: The Explore vs. Exploit Dilemma
#8genuine question (the maths lost me): this seems like a philosophical problem. Did the writing of that dilemma into mathematical language bring any interesting result, compared to using regular english ?
It's a dynamic problem. The correct choice depends on the dynamics of the system itself.
Explore vs. Exploit Dilemma is studied and simulated in computational biology. The correct strategy depends on the environment.
Re: The Explore vs. Exploit Dilemma
#9A simplified heuristic[0] for this for those interested in personal applications: it works out that you should exploit the best opportunity you come across once you’ve explored about 37% of the search space.
Re: The Explore vs. Exploit Dilemma
#10A simplified heuristic[0] for this for those interested in personal applications: it works out that you should exploit the best opportunity you come across once you’ve explored about 37% of the search space. [0]: https://en.m.wikipedia.org/wiki/Secretary_problem
With the caveat that this number is for situations where you cannot backtrack (choose a previously seen option that isn’t the current one).
There is a great book Algorithms to Live by that goes over this explore/exploit problem and more. I recommend it.