Let us say that we have some collection of players $P_0..P_{N-1}$ in a zero-sum win/loss game, and the expected win rate of $P_i$ against $P_j$ is given by $w_{ij}$. Define the skill $S_i$ of a player $P_i$ to be the average win rate against a uniformly chosen opponent, in other words $S_i = \frac{1}{N-1}\sum_{0 \le j \lt N, i \neq j} w_{ij}$. How can we determine the player with the highest skill, in the fewest number of games?

We could just repeatedly run matches between all pairs of players, but if the players vary widely in skill then most of these matches would be uninformative.

I had the idea to repeatedly sample some $P_i$ using any bandit algorithm (e.g. Thompson sampling, confidence bounds), and $P_j$ uniformly, and then only update the statistics for $P_i$. This has the advantage of focusing the search effort on the most promising candidates, but we only get half as much information per game, and sampling $P_j$ uniformly is obviously suboptimal.

We can probably improve on this by sampling $P_j$ using importance sampling based on the uncertainty in either $S_j$ or $w_{ij}$, and if we use a bandit algorithm with explicit probabilities like a softmax-based method then we can do a weighted update of the statistics of $P_j$ (although this might be high variance?).

Can anyone offer feedback on these ideas, or a suggestion of a good way to go about solving this problem?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.