Bandits without exploitation: finding the best items with incomplete information I'm trying to analyze a general game. This is probably well-known, in which case pointers to relevant literature would suffice (but explanation would not be declined!). If it's not standard, of course any help would be appreciated, even if short of a full answer.
Suppose I have N objects (say, 100) with nontrivial priors $v_1,\ldots,v_N$ representing my best guess as to their values. I have time to perform $m$ trials (say, 1000) on any of the objects, and the tests can be adaptive. I want to choose the top $k$ (say, 3) objects in order.
Each trial improves my estimate of the true value of one of the objects. But unlike the multi-armed bandit problem, there is no exploration-vs-exploitation tradeoff as such: all that matters is the list at the end of the $m$ trials. You can think of the cost function as (value of item #1 - value of item selected as #1) + ... + (value of item #$k$ - value of item selected as #$k$), so getting close is sufficient.
The priors are fairly accurate (certainly a good guide on where to search) but are subject to unknown systemic errors. The trials are unbiased but have random error. Fortunately, the random errors are the same for all trials, regardless of the object, so that seems at least somewhat statistically controllable.
I'm very much at an information-gathering point here; assume what you must to answer the question and I'll try to make it fit. :)
 A: I see two approaches here:


*

*standard stats results (concentration bounds)

*bayesian approach (since you have a prior)


The standard approach (concentration bounds)
I would be to use concentration inequalities (e.g. Hoeffding's bound) to derive a confidence interval for the true value of each object given the nber of trials you already have performed for it. The good thing with these bounds are that they hold for small samples, something that a normal or student interval don't really guarantee. Actually this is what works behind the scene of a bandit algorithm like UCB.
The Bayesian approach
Since you have a prior I would try to come back to the Thompson Sampling algorithm. Basically, you need to define a model of the value $r$ of items $E[r|\theta^*]$ with $\theta^*$ the true parameter governing the value distribution. Once you have a prior $P[\theta]$ you can use Bayes rule to update the posterior $E[\hat{\theta}|D]$ where $D$ is all the past trials and their outcome: $E[\hat{\theta}|D] \propto \prod_tE[r|\hat\theta,D]P[\theta]$, where $r$ is the outcome of the current trial. An empirical evaluation of TS and a very simple algorithm for Bernoulli rewards can be found in this paper.
Both approaches are linked to the bandits field (since it was the OP formulation), but I guess you could simply derive a bayesian algorithm given that you find a good distribution to model the value.
