論文の概要: Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox

• arxiv url: http://arxiv.org/abs/2410.05441v1
• Date: Mon, 7 Oct 2024 19:17:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-01 18:47:31.583166
• Title: Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
• Title（参考訳）: ThompsonがY Combinatorのバンドをサンプリング: 多項式レグレストとミスマッチしたサンプリングパラドックス
• Authors: Raymond Zhang, Richard Combes,
• Abstract要約: 我々は、線形半バンドと準ガウス報酬に対するトンプソンサンプリング(TS)を考える。 有限時間後悔が問題の次元と指数関数的にスケールしない最初の既知のTSを提案する。 報酬分布と正後分布からのサンプルを知れば、報酬を知らない学習者よりも指数関数的に劣る。
• 参考スコア（独自算出の注目度）: 6.382026027291193
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension of the problem. We further show the "mismatched sampling paradox": A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is available at https://github.com/RaymZhang/CTS-Mismatched-Paradox
• Abstract（参考訳）: 我々は、線形組合せ半帯域と準ガウス報酬に対するトンプソンサンプリング(TS)を考える。 有限時間後悔が問題の次元と指数関数的にスケールしない最初の既知のTSを提案する。 さらに,「ミスマッチサンプリングパラドックス」について述べる: 正後分布から報奨分布やサンプルを知る学習者は,報奨を知らない学習者よりも指数関数的に悪い結果が得られる。 実験を生成するためのコードはhttps://github.com/RaymZhang/CTS-Mismatched-Paradoxで公開されている。

関連論文リスト

• VITS : Variational Inference Thompson Sampling for contextual bandits [10.028119153832346]
  我々は、文脈的帯域幅に対するトンプソンサンプリング(TS)アルゴリズムの変種を導入・解析する。 ガウス変分推論に基づく新しいアルゴリズムであるValational Inference Thompson sample VITSを提案する。 我々は,VITS が線形文脈帯域に対して従来の TS の次元とラウンド数で同じ順序のサブ線形後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2023-07-19T17:53:22Z)
• Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback [98.29086113546045]
  本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。 RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:52:14Z)
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling [2.5496329090462626]
  グラフ理論問題に応用可能な量子インスピレーション付き古典アルゴリズムを提案する。 ガウスボソンサンプリング器で符号化されるグラフの隣接行列は非負であり、量子干渉を必要としない。
  論文  参考訳（メタデータ） (2023-02-01T16:02:31Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Algorithms for Adaptive Experiments that Trade-off Statistical Analysis with Reward: Combining Uniform Random Assignment and Reward Maximization [50.725191156128645]
  トンプソンサンプリングのようなマルチアームバンディットアルゴリズムは適応的な実験を行うのに利用できる。 統計的解析のための一様ランダム化の利点を組み合わせた2つのアルゴリズムを探索する2つのアーム実験のシミュレーションを提案する。
  論文  参考訳（メタデータ） (2021-12-15T22:11:58Z)
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits [56.31950477139053]
  半帯域フィードバック(CMAB)を用いたマルチアームバンディットの検討 我々は Combinatorial Thompson Smpling Policy (CTS) の変種を解析する。 この最終結果は,Y Combinatorial Bandit Policy (ESCB) の効率的なサンプリングに代わるものだ。
  論文  参考訳（メタデータ） (2020-06-11T17:12:11Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)

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

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