Finding the Best Dueler

Zhengu Zhang and Sheldon M. Ross ()
Additional contact information
Zhengu Zhang: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA
Sheldon M. Ross: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089, USA

Mathematics, 2023, vol. 11, issue 7, 1-12

Abstract: Consider a set of n players. We suppose that each game involves two players, that there is some unknown player who wins each game it plays with a probability greater than 1 / 2 , and that our objective is to determine this best player. Under the requirement that the policy employed guarantees a correct choice with a probability of at least some specified value, we look for a policy that has a relatively small expected number of games played before decision. We consider this problem both under the assumption that the best player wins each game with a probability of at least some specified value p 0 > 1 / 2 , and under a Bayesian assumption that the probability that player i wins a game against player j is v i v i + v j , where v 1 , … , v n are the unknown values of n independent and identically distributed exponential random variables. In the former case, we propose a policy where chosen pairs play a match that ends when one of them has had a specified number of wins more than the other; in the latter case, we propose a Thompson sampling type rule.

Keywords: best arm identification; dueling bandit (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/7/1568/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/7/1568/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:7:p:1568-:d:1105376

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().