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

31–40 of 41 posts

Re: Reinforcement Learning – Bandit Problems

#31

Post by srean »

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…

Your intuition is spot on. With this line of argument you will end up with Thompson Sampling [0]. TS is an old algorithm from the 1930s. It is disconcertingly effective, even when the underlying Bayesian assumptions are not correct. It is also extremely hard to analyze. This led to a weird state of affairs - TS gave excellent empirical performance but we could not make any theoretical statements about its efficacy. It is only very recently that this has changed.

[0] https://en.wikipedia.org/wiki/Thompson_sampling

Re: Reinforcement Learning – Bandit Problems

#32

Post by antognini »

oneraynyday wrote: post #23
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 :)

One thing that confused me is that you introduce the "preference" for an action, but don't really define it. Some exposition about what that means would have helped.

Re: Reinforcement Learning – Bandit Problems

#33

Post by lpage »

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

As a self contained, foundational course, Georgia Tech's OMSCS offering [1] is solid. Charles Isbell and Michael Littman are great at building intuition into equations.

[1] https://www.udacity.com/course/reinforcement-learning--ud600

Re: Reinforcement Learning – Bandit Problems

#34

Post by joshuamorton »

lpage wrote: post #33
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

As a self contained, foundational course, Georgia Tech's OMSCS offering [1] is solid. Charles Isbell and Michael Littman are great at building intuition into equations. [1] https://www.udacity.com/course/reinforcement-learning--ud600

Isbell's course in person was great. And if the exams for the online version are anything like the in person ones, it really does test your understanding of foundational concepts.

Re: Reinforcement Learning – Bandit Problems

#35

Post by chudi »

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…

We used it to discover the best picture of a product in terms of click trough rate, we also found that the end user really don't want you to change the order of the pictures of their products

Re: Reinforcement Learning – Bandit Problems

#36

Post by joshuamorton »

oneraynyday wrote: post #23
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 :)

Oh cool, I've also done a presentation on bandit methods for early-undergrads (see: https://gtagency.github.io/2016/experimentation-with-no-ragr..., its missing speaker notes so it looks a bit strange, but that outlines the structure fairly well). It was also sort of an intro to the beta distribution and why you should love it, hence the focus on Thompson Sampling.

Some critiques:

- I feel like your justification/explanation for why this is useful is a bit lacking. Personally I find framing it in terms of regret-minimzation better than gain-maximization, even though in practice they're the same. I think it frames the situation in such a way where you go in knowing that you will have to pick non-optimal things some, so your job is to learn the underlying distributions as quickly as possible, instead of trying to pick the best things. Interestingly, I think thinking of it as gain-maximization leads you down an epsilon greedy path, whereas regret-minimzation leads you toward UCB1/Thompson Sampling better. Since you pivot to RL instead of just bandits, I can kind of understand it, but see my last point.

- As a general rule, I try to minimize math in undergrad-focused talks/documents. Even as someone who spends a lot of time explaining statistical concepts to people, my eyes glaze over when I see `q*(a) = E[Rt|At = a]`. Obviously you need some and this is just a personal thing. For the most part I actually think you do a decent job of explaining the equations you use. At least until the gradient bandit part :P Then it just feels like a textbook proof excerpt.

- Nit: You don't fully explain that epsilon-greedy is greedy, except epsilon of the time. That caught me up for a second.

- The last thing is that I feel like the motivation and difference between stationary and nonstationary reward distributions isn't well explained. Nonstationary rewards don't really "fit" the mental model behind k-armed bandits a lot of the time. I'm actually curious for a better motivation there, as I can't articulate one myself.

Re: Reinforcement Learning – Bandit Problems

#37

Post by oneraynyday »

joshuamorton wrote: post #36
oneraynyday wrote: post #23

Earlier quoted context omitted.

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 :)

Oh cool, I've also done a presentation on bandit methods for early-undergrads (see: https://gtagency.github.io/2016/experimentation-with-no-ragr... , its missing speaker notes so it looks a bit strange, but that outlines the structure fairly well). It was also sort of an intro to the beta distribution and why you should love it, hence the focus on Thompson Sampling. Some critiques: - I feel like your justification/ex…

Hey Joshua, thanks so much for the criticism. I do see your point towards epsilon greedy vs. regret minimization. I will add a section about that before presenting UCB1. I also will add more information in the epsilon-greedy strategy section, elaborating on what the epsilon is really for. I'm not 100% sure how to reframe the nonstationary reward situation, because I feel like that adds state dependent on t to the bandit scenario, which then feels more like MDP.

Re: Reinforcement Learning – Bandit Problems

#38

Post by oneraynyday »

antognini wrote: post #32
oneraynyday wrote: post #23

Earlier quoted context omitted.

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 :)

One thing that confused me is that you introduce the "preference" for an action, but don't really define it. Some exposition about what that means would have helped.

Ah yes, I didn't want the reader to fuss too much about the idea of a preference, since it's really just an analog of un-normalized pi(modulo the exponentiation part). It doesn't have a strict definition nor is it a formal term. I will un-bold it and italicize it instead. Thank you :)

Re: Reinforcement Learning – Bandit Problems

#39

Post by joshuamorton »

oneraynyday wrote: post #37
joshuamorton wrote: post #36

Earlier quoted context omitted.

Oh cool, I've also done a presentation on bandit methods for early-undergrads (see: https://gtagency.github.io/2016/experimentation-with-no-ragr... , its missing speaker notes so it looks a bit strange, but that outlines the structure fairly well). It was also sort of an intro to the beta distribution and why you should love it, hence the focus on Thompson Sampling. Some critiques: - I feel like your justification/ex…

Hey Joshua, thanks so much for the criticism. I do see your point towards epsilon greedy vs. regret minimization. I will add a section about that before presenting UCB1. I also will add more information in the epsilon-greedy strategy section, elaborating on what the epsilon is really for. I'm not 100% sure how to reframe the nonstationary reward situation, because I feel like that adds state dependent on t to the ban…

>because I feel like that adds state dependent on t to the bandit scenario, which then feels more like MDP.

Yeah this was sort of exactly the issue I was running into. I can't justify it to myself without essentially saying "this is just an MDP in disguise", which maybe is the right way to do it. I'm pretty sure you can define a k-armed bandit as an MDP on a single state, where each action corresponds to a machine, and all actions return you to the single state.

So maybe that is the right motivation. But reversing that "an MDP is just a k-armed bandit problem where sometimes playing a machine breaks it and forces you to play other machines, which can impact how quickly the casino fixes your first machine..." feels forced.

All that said, its a good article :)

Post reply on HN