Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reinforcement Learning – Bandit Problems

oneraynyday.github.io

Post reply on HN
Print view View original

21–30 of 41 posts

Re: Reinforcement Learning – Bandit Problems

#21

Post by oneraynyday »

subatomic wrote: post #3

I was heavily into reinforcement learning around the turn of the century, and at the time, "Reinforcement Learning - An introduction" (Barto and Sutton) https://mitpress.mit.edu/books/reinforcement-learning was an absolute goldmine for me getting started. I think parts of it are online somewhere including all their pseudocode and solutions. https://mitpress.mit.edu/books/reinforcement-learning

Great suggestion! The blog was based on a large portion of the book. A friend of mine asked for a version of the first chapter that was digestible for an audience that is in high-school to undergrad college level. I wrote this blog with that in consideration, while adding my own observations as well. I am planning to write up some python solutions for the MDP chapter as well. Thanks for reading :)

Re: Reinforcement Learning – Bandit Problems

#22

Post by leongrandote »

bagrow wrote: post #15

Anyone aware of research on bandits with a growing set of arms? Meaning, every so often when you play an arm part of your reward is revealing a new arm! This seems to not fit the criteria anymore (not tabular, not Markov). Is it related to structured bandits?

If the additional arms appear late, my intuition is to use one algorithm for the old parts and one for the new arms, and a weighting factor to decide which model to use. This procedure can be generalized for generational partitions. For example you group the old arms into group A and the new arms in group B, and a bandit with two arms to decide which group to use, then inside each group you apply your favorite bandit algorithm, that is not a divide and conquer algorithm but has something in common. This is a hierarchical model.

Re: Reinforcement Learning – Bandit Problems

#23

Post by oneraynyday »

sharonzhou wrote: post #4

I'm surprised there was no octopus to represent the bandits. In all seriousness, this post makes sense to me, as someone who does RL research. However, the intuition behind the concepts could be communicated more clearly. I would reason that this piece is less accessible to those who have much less knowledge of RL/bandits. Given that it's an introduction, I presume that's your intended reader, though perhaps writing…

Thanks for the reply! My audience is for someone who is early into their undergrad degree, doing math or computer science. Which parts do you think is not communicated clearly? I can make an edit later today :)

Re: Reinforcement Learning – Bandit Problems

#24

Post by alexcnwy »

subatomic wrote: post #3

I was heavily into reinforcement learning around the turn of the century, and at the time, "Reinforcement Learning - An introduction" (Barto and Sutton) https://mitpress.mit.edu/books/reinforcement-learning was an absolute goldmine for me getting started. I think parts of it are online somewhere including all their pseudocode and solutions. https://mitpress.mit.edu/books/reinforcement-learning

Bartow & Sutton is excellent.

You can definitely find it online but be sure to find the right version - the latest version has great illustrations and is a lot clearer.

Also, check out the RL jupyter notebook here by my friend Ryan Sweke who does work on RL for quantum computing: https://github.com/R-Sweke/CrashCourseInNeuralNetworksWithKe...

Re: Reinforcement Learning – Bandit Problems

#25

Post by indescions_2018 »

Nice writeup! Why do we love bandit problems? Not only the efficacy with which agents can minimize exploration and maximize rewards in unknown worlds. But also the emergent philosophical truths that arise concerning causality!

Remains very much an active research topic. With applications ranging from epidemiology, to website optimization ;)

CS7792 - Counterfactual Machine Learning, T. Joachims, Cornell University

http://www.cs.cornell.edu/courses/cs7792/2016fa/

Deep Bayesian Bandits Showdown - Google Brain

https://arxiv.org/pdf/1802.09127.pdf

Re: Reinforcement Learning – Bandit Problems

#26

Post by levesque »

svalorzen wrote: post #10
subatomic wrote: post #3

I was heavily into reinforcement learning around the turn of the century, and at the time, "Reinforcement Learning - An introduction" (Barto and Sutton) https://mitpress.mit.edu/books/reinforcement-learning was an absolute goldmine for me getting started. I think parts of it are online somewhere including all their pseudocode and solutions. https://mitpress.mit.edu/books/reinforcement-learning

The complete first edition can be found here: http://incompleteideas.net/book/ebook/the-book.html If you're interested in some well documented C++ implementations of the algorithms shown in the book, feel free to check out https://github.com/Svalorzen/AI-Toolbox . I started the project because when I was first reading the book I had no reference implementation to compare the book to, and personally I learn better wit…

If you are going to start in RL, you should really consider reading the second edition even though it is not released yet. I am guessing that Sutton is getting closer to the finishing line as there have been numerous revisions already. The second edition has better notation and benefits from the field having matured a lot since the first book was written. http://incompleteideas.net/book/the-book-2nd.html

Re: Reinforcement Learning – Bandit Problems

#27

Post by noelwelsh »

bagrow wrote: post #15

Anyone aware of research on bandits with a growing set of arms? Meaning, every so often when you play an arm part of your reward is revealing a new arm! This seems to not fit the criteria anymore (not tabular, not Markov). Is it related to structured bandits?

Adding new arms in a bandit problem doesn't pose a problem for most bandit algorithms. Any of the common algorithms will handle it just fine. Arms disappearing is more interesting, as that effects the explore / exploit tradeoff. It's been a while since I was studying bandit algorithms but "Mortal multi-armed bandits" is one paper that addresses this.

Re: Reinforcement Learning – Bandit Problems

#28

Post by picomancer »

It seems like any method for solving this problem could be interpreted in a Bayesian way: At any time, you consider all the different possible distributions each arm could have, and assign each a probability which is how likely you think that distribution is to occur.

The probabilities are initialized to some value (the "prior"), then when you pull the arm, you get some new information, which you use to update the probabilities based on evidence.

It would be interesting to try to see if you could analytically solve this problem for a simple family of distributions. For example, assume each lever produces Gaussian results, but has an unknown mean and SD. Set the prior to be that the means are normally distributed with mean 0 and SD 1, and the SD's are exponentially distributed with mean 1.

Re: Reinforcement Learning – Bandit Problems

#29

Post by Q6T46nT668w6i3m »

crisbal_ wrote: post #7

As someone who is doing his bachelor thesis on Reinforcement Learning this is some useful information. OT (but not really) question: does anyone here use Reinforcement Learning techniques at work? For the thesis I am working on black-box optimization of 2 variable functions with Reinforcement Learning (and comparing it with Bayesian Optimization techniques). As someone else suggested the Sutton & Barto book is really…

I regularly use reinforcement methods for simple robotics problems. TensorFlow, et al. have made their use practical.

Re: Reinforcement Learning – Bandit Problems

#30

Post by xyhopguy »

picomancer wrote: post #28

It seems like any method for solving this problem could be interpreted in a Bayesian way: At any time, you consider all the different possible distributions each arm could have, and assign each a probability which is how likely you think that distribution is to occur. The probabilities are initialized to some value (the "prior"), then when you pull the arm, you get some new information, which you use to update the pr…

I think that's how you derive UCB, but optimizing cumulative regret rather than finding the probability distribution directly. Pls correct me if I'm wrong
Post reply on HN