論文の概要: Online Clustering of Bandits with Misspecified User Models

• arxiv url: http://arxiv.org/abs/2310.02717v2
• Date: Tue, 10 Oct 2023 08:59:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-13 01:45:30.436807
• Title: Online Clustering of Bandits with Misspecified User Models
• Title（参考訳）: 未特定ユーザモデルによる帯域のオンラインクラスタリング
• Authors: Zhiyong Wang, Jize Xie, Xutong Liu, Shuai Li, John C.S. Lui
• Abstract要約: コンテキスト線形バンディット(Contextual linear bandit)は、与えられた腕の特徴を学習エージェントが各ラウンドで選択し、長期の累積報酬を最大化するオンライン学習問題である。 バンディットのクラスタリング(CB)と呼ばれる一連の研究は、ユーザの好みに対する協調効果を利用しており、古典的な線形バンディットアルゴリズムよりも大幅に改善されている。 本稿では,不特定ユーザモデル (CBMUM) による盗賊のクラスタリングに関する重要な問題を初めて提示する。 モデル誤特定による不正確なユーザの選好推定と誤クラスタリングを両立できる頑健なCBアルゴリズムRCLUMBとRCLUMBを考案した。
• 参考スコア（独自算出の注目度）: 42.56440072468658
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The contextual linear bandit is an important online learning problem where given arm features, a learning agent selects an arm at each round to maximize the cumulative rewards in the long run. A line of works, called the clustering of bandits (CB), utilize the collaborative effect over user preferences and have shown significant improvements over classic linear bandit algorithms. However, existing CB algorithms require well-specified linear user models and can fail when this critical assumption does not hold. Whether robust CB algorithms can be designed for more practical scenarios with misspecified user models remains an open problem. In this paper, we are the first to present the important problem of clustering of bandits with misspecified user models (CBMUM), where the expected rewards in user models can be perturbed away from perfect linear models. We devise two robust CB algorithms, RCLUMB and RSCLUMB (representing the learned clustering structure with dynamic graph and sets, respectively), that can accommodate the inaccurate user preference estimations and erroneous clustering caused by model misspecifications. We prove regret upper bounds of $O(\epsilon_*T\sqrt{md\log T} + d\sqrt{mT}\log T)$ for our algorithms under milder assumptions than previous CB works (notably, we move past a restrictive technical assumption on the distribution of the arms), which match the lower bound asymptotically in $T$ up to logarithmic factors, and also match the state-of-the-art results in several degenerate cases. The techniques in proving the regret caused by misclustering users are quite general and may be of independent interest. Experiments on both synthetic and real-world data show our outperformance over previous algorithms.
• Abstract（参考訳）: 文脈線形帯域は、与えられた腕の特徴が与えられた場合、学習エージェントが各ラウンドの腕を選択して、長期の累積報酬を最大化する重要なオンライン学習問題である。 バンドイットのクラスタリング(cb)と呼ばれる一連の作品は、ユーザの好みに対する協調効果を利用し、古典的な線形バンドイットアルゴリズムよりも大幅に改善されている。 しかし、既存のCBアルゴリズムは明確に定義された線形ユーザモデルを必要としており、この臨界仮定が成立しない場合に失敗する可能性がある。 CBアルゴリズムが不特定ユーザモデルでより実用的なシナリオのために設計できるかどうかは未解決の問題である。 本稿では,不特定ユーザモデル (CBMUM) を用いたバンドのクラスタリングにおいて,ユーザモデルに期待される報酬を完全な線形モデルから遠ざけるという重要な問題を初めて提示する。 モデルの誤特定による不正確なユーザの選好推定と誤クラスタリングに対応する2つの頑健なCBアルゴリズムであるRCLUMBとRCLUMB(動的グラフと集合で学習されたクラスタリング構造を表現する)を考案する。 o(\epsilon_*t\sqrt{md\log t} + d\sqrt{mt}\log t)$ 従来の cb よりも穏やかな仮定の下でのアルゴリズムに対する後悔の限界(特に、腕の分布に関する制限的な技術的仮定を乗り越える)は、t$ から対数因子までの漸近的に下限に一致し、またいくつかの退化の場合における最先端の結果にも一致する。 ミスクラスタリングによる後悔を証明する技術は非常に一般的で、独立した関心事である可能性がある。 合成データと実世界のデータの両方の実験では、過去のアルゴリズムよりも性能が優れていた。

関連論文リスト

• Bad Values but Good Behavior: Learning Highly Misspecified Bandits and MDPs [16.777565006843012]
  パラメトリックな特徴に基づく報酬モデルが,帯域幅やマルコフ決定プロセス(MDP)などの意思決定設定において,さまざまなアルゴリズムによって採用されている。 我々は、$epsilon$-greedyやLinUCB、それに適合したQラーニングといった基本的なアルゴリズムが、非常に不明瞭なモデルの下で、最適ポリシーを確実に学習していることを示します。 これは、例えば、時間とともに線形にスケールする後悔の束縛を示す不特定な包帯に対する既存の最悪の結果とは対照的であり、不特定に頑丈な非自明に大規模な包帯例が存在することを示している。
  論文  参考訳（メタデータ） (2023-10-13T18:53:30Z)
• Stochastic Rising Bandits [40.32303434592863]
  本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。 この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2022-12-07T17:30:45Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
  論文  参考訳（メタデータ） (2021-11-08T18:05:35Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Fixed-Budget Best-Arm Identification in Structured Bandits [33.27743152847947]
  固定予算設定におけるベストアーム識別(BAI)は、学習エージェントが一定の回数の観測後に最適な(ベスト)腕を特定する確率を最大化する盗賊問題である。 結合一般化モデルから平均報酬推定値に基づいて最適アームを除去し,構造を組み込んだ一般トラクタブルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T01:32:43Z)
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature [61.22680308681648]
  決定論的報酬を有する1層ニューラルネットバンディットにおいても,グローバル収束は統計的に難解であることを示す。 非線形バンディットとRLの両方に対して,オンラインモデル学習者による仮想アセンジ(Virtual Ascent with Online Model Learner)というモデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-08T12:41:56Z)
• Bayes DistNet -- A Robust Neural Network for Algorithm Runtime Distribution Predictions [1.8275108630751844]
  ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。 従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。 この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
  論文  参考訳（メタデータ） (2020-12-14T01:15:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。