Consider the following adaptive strategy for sampling from a Multi Armed Bandit with $K$ arms: 1) Split the $T$ rounds into $N (\in \mathbb{N})$ disjoint intervals. Each interval is indexed by $i=1,2,\dots,N$. We assume $N$ is fixed and $T>>N$. 2) For each interval $i$, we have an allocation function $w_i: ((w_1,\bar{X}_1),(w_2,\bar{X}_2),\dots,(w_{i-1},\bar{X}_{i-1})) \to \Delta_K$, i.e, a map from the history of allocations and sample averages it decides to sample the arm $a$ in the $i^{th}$ interval according to the proportions $w_i(a)$. Here $\bar{X}_i$ denotes the $K$-dimensional vector containing the $K$ sample means (one for each arm) from the $i^{th}$ disjoint interval. Question : Does the $N$-tuple $(X_1,X_2,\dots, \bar{X}_N)$ satisfy a LDP as $T \to \infty$? If indeed it does, it would be great to get a closed form dependence on allocation functions $w_i$ in the rate function. Any sort of (reasonable) regularity assumption on arm distribution might added to derive the result. For $N=1$ it is known to be true regardless of the nature of the allocation function $w_1$. See for example [Glynn-Juneja 04][1] for a simple argument based on Gartner Ellis. Based on their work, intuitively for $N\geq 2$ it feels like the rate function should have the form : $$ \frac{1}{N}\sum^{N}_{i=1}\sum^{K}_{a=1}w_i(u_1,\dots,u_{i-1})(a)I_a(u_i) $$ where $I_a(.)$ is rate function associated with an individual arm, and the large deviation exponent for a set $A$ has the form: $$ \underset{(u_1,u_2,\dots,u_N) \in A}{inf} \frac{1}{N}\sum^{N}_{i=1}\sum^{K}_{a=1}w_i(u_1,\dots,u_{i-1})(a)I_a(u_i). $$ [1]: https://web.stanford.edu/~glynn/papers/2004/GJuneja04.pdf