両世界の長所を両立させるマルチ・デュエル・バンディット: コンドルセとボルダの目的の下で、確率的および敵対的嗜好に対する統一アルゴリズム

要約：マルチデュエリング・バンディットは、学習者が各ラウンドで m \geq 2 本のアームを選択し、勝者のみを観察するもので、順位付けや推奨システムを含む多くの応用に自然に現れます。しかし、根本的な問題は未解決のままでした。1つのアルゴリズムが、どのレジームに直面しているかを事前に知らずに、確率的環境と敵対的環境の両方で最適に機能できるのか？これに対して肯定的な回答を示し、CondorcetおよびBordaの両方の目的の下でマルチデュエリング・バンディットに対する初の best-of-both-worlds アルゴリズムを提供します。Condorcet設定では、\texttt{MetaDueling} を提案します。これは任意のデュエリング・バンディット・アルゴリズムをマルチデュエリング・バンディット・アルゴリズムに変換するブラックボックス還元で、多方向の勝者フィードバックを不偏なペアワイズ信号に変換します。これを \texttt{Versatile-DB} で具体化すると、マルチデュエリング・バンディットに対する初の best-of-both-worlds アルゴリズムが得られます：敵対的嗜好に対しては O(\sqrt{KT}) 擬似後悔を、確率的嗜好に対してはインスタンス最適な O\!\left(\sum_{i
eq a^\star} \dfrac{\log T}{\Delta_i}\right) 擬似後悔を、両方を同時に達成し、レジームを事前に知ることなく実現します。Borda設定では、\AlgBorda を提案します。これは確率的かつ敵対的なアルゴリズムで、確率的環境における後悔として O\left(K^2 \log KT + K \log^2 T + \sum_{i: \Delta_i^{\mathrm{B}} > 0} \dfrac{K\log KT}{(\Delta_i^{\mathrm{B}})^2}\right) を達成し、敵対者に対しては O\left(K \sqrt{T \log KT} + K^{1/3} T^{2/3} (\log K)^{1/3}\right) 後悔を達成します。これもレジームの事前知識なしに。Condorcet設定に対する上界と一致する下界で上界を補完します。Borda設定では、上界は下界に対してほぼ最適で（K の要因の範囲内）、文献における既知の最良の結果と一致します。