0
$\begingroup$

I'm relatively new to reinforcement learning and have the following multi-armed bandit problem:

Let's assume we have a bandit with $n$ arms. Each arms has a different reward distribution with support $[0,1]$. Further assume we follow a $\epsilon$ greedy policy, i.e. pick the arm with the highest expected reward or with a small probability $\epsilon$ pick an arm randomly. So far, so easy.

Here comes the strange part: When one arm is played we do not only observe the reward $r$ of this arm, but also the reward of all arms with reward < $r$. But not the rewards of the arms with reward > $r$.

What I have done is to update all arms whose rewards can be observed. However, the algorithm will not converge to the arm with the highest reward. Why is that? Is there any way to leverage the reward information of all observed arms? More generally, is this actually a multi-armed bandit problem or something else?

Thank you so much for your help!

$\endgroup$
  • $\begingroup$ The policy you described that you're following is actually an $\epsilon$-greedy policy, not a greedy policy. A greedy policy would always pick the arm with the highest expected reward, period. $\endgroup$ – Dennis Soemers Jan 26 '18 at 10:30
  • 1
    $\begingroup$ A reproducible code example and/or results showing a case where this does not converge to the correct solution might be helpful. Someone has voted to close this as unclear; I'm voting to leave open as to me this seems sufficiently clear. If I understand correctly, this is a multi-armed bandit where a reward is at each step generated for all arms, but we observe only those for which the reward is smaller than for the arm that was selected (so the higher values are censored). $\endgroup$ – Juho Kokkala Jan 26 '18 at 21:06
1
$\begingroup$

How do you initialize the expected rewards for all arms? In other words, in the very first iteration, when you have not made any observations at all yet, what reward does your algorithm expect to receive from each arm?

If your answer currently is to initialize everything to $0$ (which is probably the case if you didn't explicitly think about it), I'd recommend initializing everything to something more optimistic (for example, initializing all expected rewards to $1$ when you have no observations yet for an arm.

Why would this help? Consider the following easy example: we have three arms. The first arm gives a reward around $0.1$, the second around $0.5$, and the third around $0.9$. In the very first iteration, you don't have any observations, so you'll just randomly pick an arm. Suppose you initialized all expected rewards to $0$, and you random picked the second arm. This lets you observe rewards for the first two arms, for which you'll update your expectations towards $0.1$ and $0.5$. You don't observe any reward for the third arm, so that one will stay at the expected value you initialized ($0$). In your second iteration, it will be much more likely to pick arm two again, because it has the highest expected reward. If you had instead initialized all arms to an expected reward of $1$, you'd be very likely to pick the third arm in your second iteration.

This kind of optimistic initialization is almost always useful, in any kind of Multi-Armed Bandit problem. Apart from that, I suspect it may also be beneficial in your specific case to update all arms every iteration, not only the ones for which you made observations. Suppose you played an arm and observed a reward $r$. You described that you can already also observe the rewards of all other arms with rewards $< r$, and update those with the correct rewards. This actually also gives you some information about all the remaining arms, the ones with rewards $> r$, and you do not use this information to update those yet.

Now, you don't have precise information for them, you don't know exactly how much higher than $r$ they would be, but you do know that they would all have a reward of at least $r$. So, I suspect it would be useful to simply update all of those by pretending they had a reward of $r$. Alternatively, it may be worth trying to update them all with a reward of $r + \alpha$ for some small value $\alpha$, but I'm not 100% sure about that; you'd have to evaluate it empirically.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.