1
$\begingroup$

In multi-armed bandit problem, we have a set of $K$ arms. In each round $t$, a bandit selects an arm $k$ and receives a reward $r_{kt}$. The objective is to maximize the rewards after $T$ rounds.

My question: Does selecting the same arm in two different rounds leads to the same reward? Or the rewards are completely different?

It is surprising to me if one could select the same arm but receives a different reward and still has a sublinear regret.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ In one common setting, each arm is associated with a distribution $R_k$, and $r_{kt} \sim R_k$ independently for different $t$. So selecting the same arm in two different rounds doesn't necessarily lead to the same reward, but the distribution of the reward is identical. $\endgroup$
    – Yuval Filmus
    May 31, 2018 at 22:06
  • $\begingroup$ Then, I guess that in the nonstochastic multi-armed bandit problem the same arm may lead to two different rewards. Is that so? In this paper rob.schapire.net/papers/AuerCeFrSc01.pdf, it is mentioned that "after each trial $t$, we assume the player knows only the rewards of the previously chosen actions". If the same action leads to two different rewards, then such knowledge is not very useful, right? $\endgroup$
    – zdm
    Jun 1, 2018 at 14:00
  • 1
    $\begingroup$ @zdm the paper you link to uses a different model of bandits than the standard statistical one, as the paper says in its abstract. In its model, as the paper says, the rewards at different time steps are completely arbitrary except for being bounded in $[0,1]$. So they do not necessarily have any relationship to the past rewards. That's what makes the problem hard. $\endgroup$
    – usul
    Jun 1, 2018 at 14:45

1 Answer 1

Reset to default
4
$\begingroup$

In the version of the Multi-Armed Bandit problem I'm familiar with, there is a fixed list of distributions $B = R_1, R_2 \cdots R_n$, and the reward for pulling lever $k$ is chosen from the distribution $R_k$.

So pulling the same lever twice might lead to different rewards, but the rewards are connected through the distribution $R_k$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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