Given stochastic payoff functions $X_{1}(t) \dots X_{K}(t)$, each having a different probability distribution on $[0,1]$, denote the expected value of $X_i(t)$ by $\mu_i$, and define $\mu^* = \max_{i \in {1\dots K}}\mu_i$, and define the pseudoregret for a certain strategy $I_t$(which associates an integer between $1$ and $K$ with every $t$) as the following: $$ \bar{R}_n = \max_{i \in {1\dots K}} \mathbb{E}\left[ \sum_{t=1}^nX_i(t)  \sum_{t=1}^n X_{I_t}(t) \right] $$ The paper I'm reading states that this can be written as the following: $$ \bar{R}_n = n\mu^*  \sum_{t=1}^n \mathbb{E}[\mu_{I_t}] $$ Now I know where the first term comes from, but where does the double expected value come from?(note, in the paper they state that $\mu_i$ denotes the mean of $X_i(t)$ but so far as I understand mean and expected value are semantically identical. I may be wrong though.)
2
$\begingroup$
$\endgroup$
1
$\begingroup$
$\endgroup$
Since $$E(X_{I_t}\mid I_t)=\mu_{I_t},$$ by iterated expectation $$E(X_{I_t})=E(E(X_{I_t}\mid I_t)) = E(\mu_{I_t}),$$ from which we have the desired equality.


$\begingroup$ You're welcome... only 18 months later! $\endgroup$ – Bjørn KjosHanssen Mar 11 at 7:07