The dueling bandits problem is an online learning framework for learning from
pairwise preference feedback, and is particularly well-suited for modeling
settings that elicit subjective or implicit human feedback. In this paper, we
study the problem of multi-dueling bandits with dependent arms, which extends
the original dueling bandits setting by simultaneously dueling multiple arms as
well as modeling dependencies between arms. These extensions capture key
characteristics found in many real-world applications, and allow for the
opportunity to develop significantly more efficient algorithms than were
possible in the original setting. We propose the \selfsparring algorithm, which
reduces the multi-dueling bandits problem to a conventional bandit setting that
can be solved using a stochastic bandit algorithm such as Thompson Sampling,
and can naturally model dependencies using a Gaussian process prior. We present
a no-regret analysis for multi-dueling setting, and demonstrate the
effectiveness of our algorithm empirically on a wide range of simulation
settings.

本文研究具有相关性的多股臂的多对打算法，在推荐系统等领域可以更高效地学习和优化用户的基于偏好的关键特征，使用自对抗算法，结合高斯过程统计方法可以更准确地捕捉相关性，提升算法的效果。

具有相关臂的多路对决自适应波段算法

Multi-dueling Bandits with Dependent Arms

In the classic multi-armed bandits problem, the goal is to have a policy for
dynamically operating arms that each yield stochastic rewards with unknown
means. The key metric of interest is regret, defined as the gap between the
expected total reward accumulated by an omniscient player that knows the reward
means for each arm, and the expected total reward accumulated by the given
policy. The policies presented in prior work have storage, computation and
regret all growing linearly with the number of arms, which is not scalable when
the number of arms is large. We consider in this work a broad class of
multi-armed bandits with dependent arms that yield rewards as a linear
combination of a set of unknown parameters. For this general framework, we
present efficient policies that are shown to achieve regret that grows
logarithmically with time, and polynomially in the number of unknown parameters
(even though the number of dependent arms may grow exponentially). Furthermore,
these policies only require storage that grows linearly in the number of
unknown parameters. We show that this generalization is broadly applicable and
useful for many interesting tasks in networks that can be formulated as
tractable combinatorial optimization problems with linear objective functions,
such as maximum weight matching, shortest path, and minimum spanning tree
computations.

本文提出了一种适用于多臂赌博机问题的解决方案，只需要以线性时间复杂度存储未知参数，可以处理一般的掌握参数相关性的问题，并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。