The regret in a multi-arm bandit model is given by

$$\underset{j}{\max}\sum_{t=1}^{T}x_j(t) -G_{A}$$

where $$G_A=\sum_{t=1}^{T}x_{it}(t)$$ is the total reward achieved by the learner, based on an action $i$, taken at each time interval $t$, i.e $i_{t}\in {1,2,...,K}$ and $x_j(t)$ is the reward assosciated with action $j$, at time $t$ with $K$, being the total number of actions available.

In a stochastic multi-arm bandit setting where each arm is modeled by a population distribution:

a) What is the connection between the sequential decisions taken by a chosen learner that guarantees a minimization of the expectation of the above regret?

I ask this, as I do not see the expectation of the best arm being accounted for- directly in the given form of the regret. Instead, is there a bound that connects this regret to the population mean parameters?

I looked at the expected regret being $$\mathbb{E}\left[\underset{j}{\max}\sum_{t=1}^{T}x_j(t)\right]-\mathbb{E}G_A $$ and want to have a connection between the steps in any chosen multi-arm-bandit algorithm and the minimization of the expected regret. Is it done directly- or is it based on the minimization of say, an indirect upper bound?

  • 1
    $\begingroup$ Isn't the first term reflecting the best strategy, and therefore the best arm, over the period? To take the mean, you'd just multiple by 1/T, but you would need to multiply both terms by that to equivalize them. I'm not sure where you're stuck. $\endgroup$
    – Michelle
    Feb 24, 2012 at 9:10
  • $\begingroup$ The probabilities are allocated to the actions at time t+1 based on the actions in 1...t by a chosen Reinforcement Learner. The connection between these sequential actions to a minimization of the above regret alludes me. To dig in further- the Exp3 method introduced in Auer, Bianchi, Yoav Freund and Rob Schapire's work has a sequential probability allocation mechanism at each time step t. They construct a bound over the expected regret. Exp3 does not make distributional assumptions. I am interested if there are such connections between a stochastic(parametric) technique to the expected regret $\endgroup$
    – hearse
    Feb 24, 2012 at 15:22
  • $\begingroup$ @PraneethVepakomma No need to mark this post as edited directly in the title; we have access to edit history (near your user badge) for that. $\endgroup$
    – chl
    Feb 24, 2012 at 15:41

2 Answers 2


As Michelle said, the first term is the utility of the omniscient learner, and the second term is the utility of your agent. Your goal is to devise a policy---a rule to select an action $i$ at time $t$---to minimize the difference, which we call the regret.

The crux of the problem is that you don't know the optimal arm at a particular time until you play it, and that's where the expectations come in. So the problem reduces to one of estimating the best arm at any moment based on the available information.

  • 2
    $\begingroup$ @PraneethVepakomma It is an old monograph and I don't know whether or not it formally addresses your issue but have you seen Don Berry's book "Bandit Problems"? I think it was published by Chapman and Hall. $\endgroup$ Jun 2, 2012 at 0:04
  • $\begingroup$ Thanks for the pointer. I will search for this material. $\endgroup$
    – hearse
    Jun 12, 2012 at 19:06

I have understood this far- recently-looking for the difference between $\mathbb{E}[ \max_j \sum_{j=1}^T x_j(t) - G_A(T) ]$ and $\max_j \mathbb{E}[ \sum_{j=1}^T x_j(t) - G_A(T) ]$ obviously, the first one is greater. This is because $\mathbb{E}[\max_{j} Z_{j}] \ge \max_j \mathbb{E}[ Z_j ]$ Thus, if we prove that an algorithm controls the first "expected regret" then it will obviously control the second one (control the regret== To prove an upper bound for the regret).


Your Answer

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

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