論文の概要: Borda Regret Minimization for Generalized Linear Dueling Bandits
- arxiv url: http://arxiv.org/abs/2303.08816v1
- Date: Wed, 15 Mar 2023 17:59:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-16 12:46:43.836984
- Title: Borda Regret Minimization for Generalized Linear Dueling Bandits
- Title（参考訳）: 一般化線形デュリングバンディットに対するボルダ後悔最小化
- Authors: Yue Wu and Tao Jin and Hao Lou and Farzad Farnoud and Quanquan Gu
- Abstract要約: 本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
既存のモデルの多くをカバーする新しい,表現力の高い線形デュエルバンドモデルを提案する。
- 参考スコア（独自算出の注目度）: 80.45695803272736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Dueling bandits are widely used to model preferential feedback that is
prevalent in machine learning applications such as recommendation systems and
ranking. In this paper, we study the Borda regret minimization problem for
dueling bandits, which aims to identify the item with the highest Borda score
while minimizing the cumulative regret. We propose a new and highly expressive
generalized linear dueling bandits model, which covers many existing models.
Surprisingly, the Borda regret minimization problem turns out to be difficult,
as we prove a regret lower bound of order $\Omega(d^{2/3} T^{2/3})$, where $d$
is the dimension of contextual vectors and $T$ is the time horizon. To attain
the lower bound, we propose an explore-then-commit type algorithm, which has a
nearly matching regret upper bound $\tilde{O}(d^{2/3} T^{2/3})$. When the
number of items/arms $K$ is small, our algorithm can achieve a smaller regret
$\tilde{O}( (d \log K)^{1/3} T^{2/3})$ with proper choices of hyperparameters.
We also conduct empirical experiments on both synthetic data and a simulated
real-world environment, which corroborate our theoretical analysis.
- Abstract（参考訳）: デュエルバンディットは、レコメンデーションシステムやランキングのような機械学習アプリケーションで広く使われている優先的なフィードバックをモデル化するために広く使われている。
本稿では,ボルダの残忍度を最小化しつつ,最も高いボルダスコアの項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,既存のモデルの多くをカバーする新しい表現力に富んだ一般化線形デュリングバンディットモデルを提案する。
驚いたことに、ボルダの後悔の最小化問題は、次数$\Omega(d^{2/3} T^{2/3})$、$d$は文脈ベクトルの次元、$T$は時間地平線であることを示すため、困難であることが判明した。
下界を得るために、ほぼ一致した後悔の上界$\tilde{O}(d^{2/3} T^{2/3})$を持つ探索列コミット型アルゴリズムを提案する。
K$のアイテム/アームの数が小さい場合、我々のアルゴリズムは、ハイパーパラメータの適切な選択で小さな後悔$\tilde{O}( (d \log K)^{1/3} T^{2/3})$を達成することができる。
また, 合成データと実世界のシミュレーション環境の両方について実験を行い, 理論解析を裏付ける実験を行った。
関連論文リスト
- Horizon-Free Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Better Best of Both Worlds Bounds for Bandits with Switching Costs [37.71741656687868]
本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。
本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
論文 参考訳（メタデータ） (2022-06-07T08:22:56Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。
低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-04T15:30:14Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-20T06:36:19Z) - Regret Minimization in Partially Observable Linear Quadratic Control [91.43582419264763]
モデル力学が未知の先行性を持つ場合、部分的に観測可能な線形二次制御系における後悔の問題を考察する。
本稿では, 部分的に観測可能な線形二次制御のために, 後悔を分解し, 終端から終端までの後悔の上限を与える新しい方法を提案する。
論文 参考訳（メタデータ） (2020-01-31T22:35:08Z) - Naive Exploration is Optimal for Online LQR [56.12283443161479]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。