Return to Question

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 1: Does the $N$-tuple $(\bar{X}_1,\bar{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 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,a}) $$ 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,a}). $$

This form has an intuitive appeal- we take the deviations of each arm in a disjoint interval $i$ and then sum them across arms and intervals in an appropriate weighted manner.

For $N=2$, I feel one can again use Gartner Ellis in the following nested manner:

Consider the mgf for $(\bar{X}_1,\bar{X}_2)$:

\begin{aligned} e^{\Lambda_T(T\lambda)}&=E[e^{\langle T \lambda,(\bar{X}_1,\bar{X}_2)\rangle}]\\ &=\int e^{\langle T \lambda_1,u_1\rangle}E[e^{\langle T \lambda_2,\bar{X}_2\rangle}|\bar{X}_1=u_1]\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{\langle T \lambda_1,u_1\rangle}e^{T/2\cdot(\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1) \end{aligned} where $\Lambda$'s are the appropriate cumulant functions for various distributions. Now from the result of $N=1$ we note that the family of measures $(\mathbb{P}_T(\bar{X}_1 \in \cdot))_{T \in \mathbb{N}}$ satisfies an LDP with rate function: $$ \frac{1}{2}\sum_a w_1(a)I_a(.) $$ and hence one can invoke Varadhan's lemma to evaluate the limit: \begin{aligned} \underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}&=\underset{T \to \infty}{lim}\frac{\log\big( \int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\big)}{T}\\ &=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a}) \end{aligned}

Thus the usual Gartner Ellis limit will exist and $(\bar{X}_1,\bar{X}_2)$ will satisfy a LDP with rate function which is the fenchel conjugate of the above limit.

Question 2: Is the above obtained rate function just a disguised version of the heuristic guess we have for $N=2$? I haven't been able to relate the two rate functions.

Edit: Let us denote: $$ \Lambda(\lambda)=\underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a})) $$ The fenchel conjugate of this limiting cumulant function then is: $$ \Lambda^{*}(v_1,v_2)=\underset{\lambda}{sup}(\langle \lambda_1,v_1 \rangle+\langle \lambda_2,v_2 \rangle-\Lambda(\lambda)) $$

But from the variational form of $\Lambda(\lambda)$ we have: $$ \Lambda(\lambda) \geq \langle \lambda_1,v_1\rangle+\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}) $$ Hence we have that: \begin{aligned} \Lambda^{*}(v_1,v_2) &\leq \underset{\lambda}{sup}(\langle \lambda_2,v_2 \rangle-\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))+\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))\\ &=\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))+\frac{1}{2}\sum_a w_2(v_1)(a)I_a(v_{2,a})) \end{aligned}

Hence the Question 2 is false. For N=2 the rate function seems to take the form : \begin{equation*} I(v_1,v_2)=\Lambda^{*}(v_1,v_2)= \begin{cases} +\infty & v_1 \neq u^{*}_1 \\ \frac{1}{2}\sum_a w_1(a)I_a(u^{*}_{1,a}))+\frac{1}{2}\sum_a w_2(u^{*}_1)(a)I_a(v_{2,a})) & v_1 =u^{*}_1 \end{cases} \end{equation*} where $u^{*}_1$ is the maximiser of the optimization: $$ \underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a})) $$

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 1: Does the $N$-tuple $(\bar{X}_1,\bar{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 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,a}) $$ 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,a}). $$

This form has an intuitive appeal- we take the deviations of each arm in a disjoint interval $i$ and then sum them across arms and intervals in an appropriate weighted manner.

For $N=2$, I feel one can again use Gartner Ellis in the following nested manner:

Consider the mgf for $(\bar{X}_1,\bar{X}_2)$:

\begin{aligned} e^{\Lambda_T(T\lambda)}&=E[e^{\langle T \lambda,(\bar{X}_1,\bar{X}_2)\rangle}]\\ &=\int e^{\langle T \lambda_1,u_1\rangle}E[e^{\langle T \lambda_2,\bar{X}_2\rangle}|\bar{X}_1=u_1]\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{\langle T \lambda_1,u_1\rangle}e^{T/2\cdot(\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1) \end{aligned} where $\Lambda$'s are the appropriate cumulant functions for various distributions. Now from the result of $N=1$ we note that the family of measures $(\mathbb{P}_T(\bar{X}_1 \in \cdot))_{T \in \mathbb{N}}$ satisfies an LDP with rate function: $$ \frac{1}{2}\sum_a w_1(a)I_a(.) $$ and hence one can invoke Varadhan's lemma to evaluate the limit: \begin{aligned} \underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}&=\underset{T \to \infty}{lim}\frac{\log\big( \int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\big)}{T}\\ &=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a}) \end{aligned}

Thus the usual Gartner Ellis limit will exist and $(\bar{X}_1,\bar{X}_2)$ will satisfy a LDP with rate function which is the fenchel conjugate of the above limit.

Question 2: Is the above obtained rate function just a disguised version of the heuristic guess we have for $N=2$? I haven't been able to relate the two rate functions.

Edit: Let us denote: $$ \Lambda(\lambda)=\underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a})) $$ The fenchel conjugate of this limiting cumulant function then is: $$ \Lambda^{*}(v_1,v_2)=\underset{\lambda}{sup}(\langle \lambda_1,v_1 \rangle+\langle \lambda_2,v_2 \rangle-\Lambda(\lambda)) $$

But from the variational form of $\Lambda(\lambda)$ we have: $$ \Lambda(\lambda) \geq \langle \lambda_1,v_1\rangle+\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}) $$ Hence we have that: \begin{aligned} \Lambda^{*}(v_1,v_2) &\leq \underset{\lambda}{sup}(\langle \lambda_2,v_2 \rangle-\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))+\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))\\ &=\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))+\frac{1}{2}\sum_a w_2(v_1)(a)I_a(v_{2,a})) \end{aligned}

Hence the Question 2 is false.

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 1: Does the $N$-tuple $(\bar{X}_1,\bar{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 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,a}) $$ 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,a}). $$

This form has an intuitive appeal- we take the deviations of each arm in a disjoint interval $i$ and then sum them across arms and intervals in an appropriate weighted manner.

For $N=2$, I feel one can again use Gartner Ellis in the following nested manner:

Consider the mgf for $(\bar{X}_1,\bar{X}_2)$:

\begin{aligned} e^{\Lambda_T(T\lambda)}&=E[e^{\langle T \lambda,(\bar{X}_1,\bar{X}_2)\rangle}]\\ &=\int e^{\langle T \lambda_1,u_1\rangle}E[e^{\langle T \lambda_2,\bar{X}_2\rangle}|\bar{X}_1=u_1]\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{\langle T \lambda_1,u_1\rangle}e^{T/2\cdot(\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1) \end{aligned} where $\Lambda$'s are the appropriate cumulant functions for various distributions. Now from the result of $N=1$ we note that the family of measures $(\mathbb{P}_T(\bar{X}_1 \in \cdot))_{T \in \mathbb{N}}$ satisfies an LDP with rate function: $$ \frac{1}{2}\sum_a w_1(a)I_a(.) $$ and hence one can invoke Varadhan's lemma to evaluate the limit: \begin{aligned} \underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}&=\underset{T \to \infty}{lim}\frac{\log\big( \int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\big)}{T}\\ &=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a}) \end{aligned}

Thus the usual Gartner Ellis limit will exist and $(\bar{X}_1,\bar{X}_2)$ will satisfy a LDP with rate function which is the fenchel conjugate of the above limit.

Question 2: Is the above obtained rate function just a disguised version of the heuristic guess we have for $N=2$? I haven't been able to relate the two rate functions.

Edit: Let us denote: $$ \Lambda(\lambda)=\underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a})) $$ The fenchel conjugate of this limiting cumulant function then is: $$ \Lambda^{*}(v_1,v_2)=\underset{\lambda}{sup}(\langle \lambda_1,v_1 \rangle+\langle \lambda_2,v_2 \rangle-\Lambda(\lambda)) $$

But from the variational form of $\Lambda(\lambda)$ we have: $$ \Lambda(\lambda) \geq \langle \lambda_1,v_1\rangle+\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}) $$ Hence we have that: \begin{aligned} \Lambda^{*}(v_1,v_2) &\leq \underset{\lambda}{sup}(\langle \lambda_2,v_2 \rangle-\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))+\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))\\ &=\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))+\frac{1}{2}\sum_a w_2(v_1)(a)I_a(v_{2,a})) \end{aligned}

Hence the Question 2 is false. For N=2 the rate function seems to take the form : \begin{equation*} I(v_1,v_2)=\Lambda^{*}(v_1,v_2)= \begin{cases} +\infty & v_1 \neq u^{*}_1 \\ \frac{1}{2}\sum_a w_1(a)I_a(u^{*}_{1,a}))+\frac{1}{2}\sum_a w_2(u^{*}_1)(a)I_a(v_{2,a})) & v_1 =u^{*}_1 \end{cases} \end{equation*} where $u^{*}_1$ is the maximiser of the optimization: $$ \underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a}) $$

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 1: Does the $N$-tuple $(\bar{X}_1,\bar{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 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,a}) $$ 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,a}). $$

This form has an intuitive appeal- we take the deviations of each arm in a disjoint interval $i$ and then sum them across arms and intervals in an appropriate weighted manner.

For $N=2$, I feel one can again use Gartner Ellis in the following nested manner:

Consider the mgf for $(\bar{X}_1,\bar{X}_2)$:

\begin{aligned} e^{\Lambda_T(T\lambda)}&=E[e^{\langle T \lambda,(\bar{X}_1,\bar{X}_2)\rangle}]\\ &=\int e^{\langle T \lambda_1,u_1\rangle}E[e^{\langle T \lambda_2,\bar{X}_2\rangle}|\bar{X}_1=u_1]\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{\langle T \lambda_1,u_1\rangle}e^{T/2\cdot(\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1) \end{aligned} where $\Lambda$'s are the appropriate cumulant functions for various distributions. Now from the result of $N=1$ we note that the family of measures $(\mathbb{P}_T(\bar{X}_1 \in \cdot))_{T \in \mathbb{N}}$ satisfies an LDP with rate function: $$ \frac{1}{2}\sum_a w_1(a)I_a(.) $$ and hence one can invoke Varadhan's lemma to evaluate the limit: \begin{aligned} \underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}&=\underset{T \to \infty}{lim}\frac{\log\big( \int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\big)}{T}\\ &=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a}) \end{aligned}

Thus the usual Gartner Ellis limit will exist and $(\bar{X}_1,\bar{X}_2)$ will satisfy a LDP with rate function which is the fenchel conjugate of the above limit.

Question 2: Is the above obtained rate function just a disguised version of the heuristic guess we have for $N=2$? I haven't been able to relate the two rate functions.

Edit: Let us denote: $$ \Lambda(\lambda)=\underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a})) $$ The fenchel conjugate of this limiting cumulant function then is: $$ \Lambda^{*}(v_1,v_2)=\underset{\lambda}{sup}(\langle \lambda_1,v_1 \rangle+\langle \lambda_2,v_2 \rangle-\Lambda(\lambda)) $$

But from the variational form of $\Lambda(\lambda)$ we have: $$ \Lambda(\lambda) \geq \langle \lambda_1,v_1\rangle+\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}) $$ Hence we have that: \begin{aligned} \Lambda^{*}(v_1,v_2) &\leq \underset{\lambda}{sup}(\langle \lambda_2,v_2 \rangle-\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))+\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))\\ &=\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))+\frac{1}{2}\sum_a w_2(v_1)(a)I_a(v_{2,a})) \end{aligned}

Hence the Question 2 is false. For N=2 the rate function seems to take the form : \begin{equation*} I(v_1,v_2)=\Lambda^{*}(v_1,v_2)= \begin{cases} +\infty & v_1 \neq u^{*}_1 \\ \frac{1}{2}\sum_a w_1(a)I_a(u^{*}_{1,a}))+\frac{1}{2}\sum_a w_2(u^{*}_1)(a)I_a(v_{2,a})) & v_1 =u^{*}_1 \end{cases} \end{equation*} where $u^{*}_1$ is the maximiser of the optimization: $$ \underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a})) $$

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 1: Does the $N$-tuple $(\bar{X}_1,\bar{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 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,a}) $$ 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,a}). $$

This form has an intuitive appeal- we take the deviations of each arm in a disjoint interval $i$ and then sum them across arms and intervals in an appropriate weighted manner.

For $N=2$, I feel one can again use Gartner Ellis in the following nested manner:

Consider the mgf for $(\bar{X}_1,\bar{X}_2)$:

\begin{aligned} e^{\Lambda_T(T\lambda)}&=E[e^{\langle T \lambda,(\bar{X}_1,\bar{X}_2)\rangle}]\\ &=\int e^{\langle T \lambda_1,u_1\rangle}E[e^{\langle T \lambda_2,\bar{X}_2\rangle}|\bar{X}_1=u_1]\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{\langle T \lambda_1,u_1\rangle}e^{T/2\cdot(\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1) \end{aligned} where $\Lambda$'s are the appropriate cumulant functions for various distributions. Now from the result of $N=1$ we note that the family of measures $(\mathbb{P}_T(\bar{X}_1 \in \cdot))_{T \in \mathbb{N}}$ satisfies an LDP with rate function: $$ \frac{1}{2}\sum_a w_1(a)I_a(.) $$ and hence one can invoke Varadhan's lemma to evaluate the limit: \begin{aligned} \underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}&=\underset{T \to \infty}{lim}\frac{\log\big( \int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\big)}{T}\\ &=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a}) \end{aligned}

Thus the usual Gartner Ellis limit will exist and $(\bar{X}_1,\bar{X}_2)$ will satisfy a LDP with rate function which is the fenchel conjugate of the above limit.

Question 2: Is the above obtained rate function just a disguised version of the heuristic guess we have for $N=2$? I haven't been able to relate the two rate functions.

Edit: Let us denote: $$ \Lambda(\lambda)=\underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a})) $$ The fenchel conjugate of this limiting cumulant function then is: $$ \Lambda^{*}(v_1,v_2)=\underset{\lambda}{sup}(\langle \lambda_1,v_1 \rangle+\langle \lambda_2,v_2 \rangle-\Lambda(\lambda)) $$

But from the variational form of $\Lambda(\lambda)$ we have: $$ \Lambda(\lambda) \geq \langle \lambda_1,v_1\rangle+\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}) $$ Hence we have that: \begin{aligned} \Lambda^{*}(v_1,v_2) &\leq \underset{\lambda}{sup}(\langle \lambda_2,v_2 \rangle-\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))+\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))\\ &=\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))+\frac{1}{2}\sum_a w_2(v_1)(a)I_a(v_1)(a)) \end{aligned}

Hence the Question 2 is false.

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 1: Does the $N$-tuple $(\bar{X}_1,\bar{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 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,a}) $$ 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,a}). $$

This form has an intuitive appeal- we take the deviations of each arm in a disjoint interval $i$ and then sum them across arms and intervals in an appropriate weighted manner.

For $N=2$, I feel one can again use Gartner Ellis in the following nested manner:

Consider the mgf for $(\bar{X}_1,\bar{X}_2)$:

\begin{aligned} e^{\Lambda_T(T\lambda)}&=E[e^{\langle T \lambda,(\bar{X}_1,\bar{X}_2)\rangle}]\\ &=\int e^{\langle T \lambda_1,u_1\rangle}E[e^{\langle T \lambda_2,\bar{X}_2\rangle}|\bar{X}_1=u_1]\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{\langle T \lambda_1,u_1\rangle}e^{T/2\cdot(\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\\ &=\int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1) \end{aligned} where $\Lambda$'s are the appropriate cumulant functions for various distributions. Now from the result of $N=1$ we note that the family of measures $(\mathbb{P}_T(\bar{X}_1 \in \cdot))_{T \in \mathbb{N}}$ satisfies an LDP with rate function: $$ \frac{1}{2}\sum_a w_1(a)I_a(.) $$ and hence one can invoke Varadhan's lemma to evaluate the limit: \begin{aligned} \underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}&=\underset{T \to \infty}{lim}\frac{\log\big( \int e^{T(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))}\mathbb{P}_T(\bar{X}_1 \in du_1)\big)}{T}\\ &=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a}) \end{aligned}

Thus the usual Gartner Ellis limit will exist and $(\bar{X}_1,\bar{X}_2)$ will satisfy a LDP with rate function which is the fenchel conjugate of the above limit.

Question 2: Is the above obtained rate function just a disguised version of the heuristic guess we have for $N=2$? I haven't been able to relate the two rate functions.

Edit: Let us denote: $$ \Lambda(\lambda)=\underset{T \to \infty}{lim}\frac{\Lambda_T(T\lambda)}{T}=\underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a})) $$ The fenchel conjugate of this limiting cumulant function then is: $$ \Lambda^{*}(v_1,v_2)=\underset{\lambda}{sup}(\langle \lambda_1,v_1 \rangle+\langle \lambda_2,v_2 \rangle-\Lambda(\lambda)) $$

But from the variational form of $\Lambda(\lambda)$ we have: $$ \Lambda(\lambda) \geq \langle \lambda_1,v_1\rangle+\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}) $$ Hence we have that: \begin{aligned} \Lambda^{*}(v_1,v_2) &\leq \underset{\lambda}{sup}(\langle \lambda_2,v_2 \rangle-\frac{1}{2}\sum_a w_2(v_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(v_1)(a))+\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))\\ &=\frac{1}{2}\sum_a w_1(a)I_a(v_{1,a}))+\frac{1}{2}\sum_a w_2(v_1)(a)I_a(v_{2,a})) \end{aligned}

Hence the Question 2 is false. For N=2 the rate function seems to take the form : \begin{equation*} I(v_1,v_2)=\Lambda^{*}(v_1,v_2)= \begin{cases} +\infty & v_1 \neq u^{*}_1 \\ \frac{1}{2}\sum_a w_1(a)I_a(u^{*}_{1,a}))+\frac{1}{2}\sum_a w_2(u^{*}_1)(a)I_a(v_{2,a})) & v_1 =u^{*}_1 \end{cases} \end{equation*} where $u^{*}_1$ is the maximiser of the optimization: $$ \underset{u_1}{sup}(\langle \lambda_1,u_1\rangle+\frac{1}{2}\sum_a w_2(u_1)(a)\Lambda_a(2\lambda_{2,a}/w_2(u_1)(a))-\frac{1}{2}\sum_a w_1(a)I_a(u_{1,a}) $$