# Why is this regret a good choice for a multi-armed bandit?

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?

-
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. –  Michelle Feb 24 '12 at 9:10
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 –  PraneethVepakomma Feb 24 '12 at 15:22
@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. –  chl Feb 24 '12 at 15:41
That's cool. Thanks. –  PraneethVepakomma Feb 24 '12 at 15:46

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

-
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.