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

11–20 of 41 posts

Re: Reinforcement Learning – Bandit Problems

#11

Post by leongrandote »

svalorzen wrote: post #8
leongrandote wrote: post #6

At the beginning of this post the given definition of value doesn't seem correct to me, because I think it should be the expected value of the sum of all the rewards from t to infinity and not of R_t, but I could be wrong. Citing D. Silver: The agent's job is to maximise cumulative rewards (highlight cumulative). I would suggest David Silver course for reinforcement learning, http://www0.cs.ucl.ac.uk/staff/d.silver/w…

You are right, it should be the expected value for the sum of all future rewards. At the same time, given that we're talking about bandits, it doesn't really matter, since there is no state. Thus, the summatory over time you'd like to see doesn't change the relative ordering of the actions: the expected value in your definition is simply the expected reward for the action multiplied by the number of times you expect…

You are right, anyway I think that people playing with a bandit machine are going to continue playing more time if they are getting a lot of money that if they are loosing money, so when people are involved in games there is a hidden state, the mental state of the player. But if you decide up front the number of steps and you don't change your strategy depending of your mood, then this formal algorithm work as stated.

Re: Reinforcement Learning – Bandit Problems

#12

Post by banditlover »

leongrandote wrote: post #11
svalorzen wrote: post #8

Earlier quoted context omitted.

You are right, it should be the expected value for the sum of all future rewards. At the same time, given that we're talking about bandits, it doesn't really matter, since there is no state. Thus, the summatory over time you'd like to see doesn't change the relative ordering of the actions: the expected value in your definition is simply the expected reward for the action multiplied by the number of times you expect…

You are right, anyway I think that people playing with a bandit machine are going to continue playing more time if they are getting a lot of money that if they are loosing money, so when people are involved in games there is a hidden state, the mental state of the player. But if you decide up front the number of steps and you don't change your strategy depending of your mood, then this formal algorithm work as stated…

Contextual bandits, on the other hand, allow you to put your mood as a context (features) and your strategy depends on the features. You still have that simple expectation maximization (instead of a brutally hard to optimize loss), yet much more flexibility.

Re: Reinforcement Learning – Bandit Problems

#13

Post by markatkinson »

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

Thanks for this, I have read a couple books on deep learning but struggled to find anything on Reinforcement Learning. Maybe an Ask HN is in order.

Re: Reinforcement Learning – Bandit Problems

#14

Post by subroutine »

This is interesting. It reminds me of the Rescorla-Wagner model (a model of classical conditioning that's probably mentioned in every psych/neuro learning and memory course textbook), which describes the trial-by-trial change in associative strength between a conditioned stimulus (CS) and unconditioned stimulus (US).

Though it has its shortcomings, R&M is quite elegant in its simplicity, while doing a pretty good job modeling some fairly complex behavioral/cognitive changes (and made an interesting prediction about 'blocking' that ended up being true).

For more on this...

http://campus.albion.edu/wjwilson/files/2012/03/RWSimplified...

http://www.scholarpedia.org/article/Rescorla-Wagner_model

Re: Reinforcement Learning – Bandit Problems

#15

Post by bagrow »

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?

Re: Reinforcement Learning – Bandit Problems

#16

Post by dhotson »

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?

Hmm, perhaps something like UCB1? The UCB (upper-confidence-bound) family of algorithms might be appropriate—it's not quite what you've described though.

They'll explore the arm with the highest potential payoff i.e. the highest upper-confidence-bound, which often is the arm you know the least about since they're roughly calculated as (average + confidence interval) and early on the confidence bound is large. This style of algorithm means you can add arms as you go through the experiment and they'll be explored/exploited in a reasonable way.

What you're describing sounds more like you're exploring a frontier and "discovering" new options along the way..?

Re: Reinforcement Learning – Bandit Problems

#17

Post by closed »

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?

I don't work in this area, but googled for HMM + indian buffet process and found this page. I'd guess some of the nonparametric bayesian models focus on the problem you mentioned.

http://research.cs.rutgers.edu/~cmansley/fall08/cs500.html

Re: Reinforcement Learning – Bandit Problems

#18

Post by closed »

subroutine wrote: post #14

This is interesting. It reminds me of the Rescorla-Wagner model (a model of classical conditioning that's probably mentioned in every psych/neuro learning and memory course textbook), which describes the trial-by-trial change in associative strength between a conditioned stimulus (CS) and unconditioned stimulus (US). Though it has its shortcomings, R&M is quite elegant in its simplicity, while doing a pretty good job…

RL can be seen as a generalization of the Rescorla-Wagner model!

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4633133/

Re: Reinforcement Learning – Bandit Problems

#19

Post by nabla9 »

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?

Consider any arm not pulled is "a new arm". A growing set of arms is similar to case where k >> T. This creates innovate vs. exploit problem. The learner must choose between exploiting what it already knows and searching for better rewards.

Variations of this scheme include exploit vs. copy vs. innovate used in computational biology. Learning agent can copy what others do or innovate and try something new.

Re: Reinforcement Learning – Bandit Problems

#20

Post by oneraynyday »

svalorzen wrote: post #8
leongrandote wrote: post #6

At the beginning of this post the given definition of value doesn't seem correct to me, because I think it should be the expected value of the sum of all the rewards from t to infinity and not of R_t, but I could be wrong. Citing D. Silver: The agent's job is to maximise cumulative rewards (highlight cumulative). I would suggest David Silver course for reinforcement learning, http://www0.cs.ucl.ac.uk/staff/d.silver/w…

You are right, it should be the expected value for the sum of all future rewards. At the same time, given that we're talking about bandits, it doesn't really matter, since there is no state. Thus, the summatory over time you'd like to see doesn't change the relative ordering of the actions: the expected value in your definition is simply the expected reward for the action multiplied by the number of times you expect…

Yes, it is as you stated. Due to the fact that bandits are stateless, there is no state parameter in $q_(a,s)$. From where I learned it, this could arguably be an abuse of notation to use $q_$ in the same context. In my newer entry(which is currently WIP), it uses $q_*(a,s)$ and uses cumulative sum of the future rewards(with discount). Thanks for the reply guys :)
Post reply on HN