Consider a finite time horizon $T$. Let there be $N$ Bernoulli distributions with unknown means $\nu_n=\text{Bern}(\mu_n)$ (although we can assume a prior if necessary). In each iteration $t$, we draw samples from the distributions through choice of binary variables $x_n(t)\in\{0,1\}$, if $x_n(t) = 0$ we do not draw a sample from $\nu_n$, if $x_n(t) = 1$ we draw a sample from $\nu_n$, which we denote $Z_n(t)\sim\nu_n$. All samples are independent. In each iteration, the binary variables are constrained to satisfy the constraints \begin{align*} \sum_{n\in C_i}x_n(t)\le c_i \end{align*} for all $i$, where each $C_i\subseteq\{1,\ldots,N\}$ and $c_i\in\mathbb{N}$. Assume that there exists a feasible $x(t) = (x_1(t),\ldots,x_N(t))$ in each iteration. The drawn samples are used to update the empirical means as \begin{align*} \hat \mu_n(t) = \frac{1}{T_n(t)}\sum_{s=1}^{T_n(t)}Z_n(s) \end{align*} where $T_n(t)$ denotes the number of times distribution $n$ has been sampled by time $t$, that is $T_n(t) = \sum_{s=1}^tx_n(s)$.

I am trying to devise an algorithm that finds the subset of distributions with means above a given value, call it $\mu^*$. Note that we do not know the means $\mu_n$'s, they must be estimated.

Question: Can we approach this problem using dynamic programming? I'm not looking for a complete solution, just some ideas that I can pursue and work through.

Edit: Some potentially useful facts

  1. The empirical mean estimates obey the following recursive equation \begin{align*} \hat\mu_n(t+1) = \frac{x_n(t)Z_n(t)+T_n(t-1)\hat\mu_n(t)}{x_n(t)+T_n(t-1)} =:f\big(\hat\mu_n(t),x_n(t),T_n(t-1)\big) \end{align*}
  2. Finding the means above $\mu^*$ is equivalent to finding the subset of indices where the sum of terms $\hat\mu_n(T) - \mu^*$ is maximized

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.