論文の概要: Optimal Learning for Structured Bandits

• arxiv url: http://arxiv.org/abs/2007.07302v2
• Date: Wed, 29 Sep 2021 21:13:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-10 14:26:03.883410
• Title: Optimal Learning for Structured Bandits
• Title（参考訳）: 構造化バンディットの最適学習
• Authors: Bart P.G. Van Parys, Negin Golrezaei
• Abstract要約: 本研究では,構造情報の存在下での不確実性の下でのオンライン意思決定の問題である,構造化されたマルチアームバンディットについて検討する。 そこで本稿では,情報理論的後悔を一定要素に制限した情報理論的後悔を解き明かし,幅広い構造情報を扱えるDUSAと呼ぶ新しい学習アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 6.370905925442655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study structured multi-armed bandits, which is the problem of online decision-making under uncertainty in the presence of structural information. In this problem, the decision-maker needs to discover the best course of action despite observing only uncertain rewards over time. The decision-maker is aware of certain structural information regarding the reward distributions and would like to minimize their regret by exploiting this information, where the regret is its performance difference against a benchmark policy that knows the best action ahead of time. In the absence of structural information, the classical upper confidence bound (UCB) and Thomson sampling algorithms are well known to suffer only minimal regret. As recently pointed out, neither algorithms are, however, capable of exploiting structural information that is commonly available in practice. We propose a novel learning algorithm that we call DUSA whose worst-case regret matches the information-theoretic regret lower bound up to a constant factor and can handle a wide range of structural information. Our algorithm DUSA solves a dual counterpart of the regret lower bound at the empirical reward distribution and follows its suggested play. Our proposed algorithm is the first computationally viable learning policy for structured bandit problems that has asymptotic minimal regret.
• Abstract（参考訳）: 本研究では,構造情報の存在下での不確実性下におけるオンライン意思決定の問題である構造化マルチアームバンディットについて検討する。 この問題では、意思決定者は、不確定な報酬だけを観察しながらも、最善の行動経路を見つける必要がある。 意思決定者は報酬分布に関する一定の構造的情報を認識しており、この情報を活用することで、その後悔を最小限に抑えたいと願っている。 構造情報がない場合、古典的な上層信頼境界(UCB)とトムソンサンプリングアルゴリズムは、最小限の後悔に悩まされることが知られている。 しかし、最近指摘されたように、どちらのアルゴリズムも実際には一般に利用可能な構造情報を利用することができない。 そこで本稿では,情報理論的後悔を一定要素に制限した情報理論的後悔を解き明かし,幅広い構造情報を扱えるDUSAと呼ぶ新しい学習アルゴリズムを提案する。 我々のアルゴリズムであるdusaは,経験的報酬分布における後悔の下限の二重対を解き,その遊びを追従する。 提案アルゴリズムは,漸近的最小限の後悔を伴い,構造化バンディット問題に対する最初の計算可能学習ポリシーである。

関連論文リスト

• Capsa: A Unified Framework for Quantifying Risk in Deep Neural Networks [142.67349734180445]
  ディープニューラルネットワークにリスク認識を提供する既存のアルゴリズムは複雑でアドホックである。 ここでは、リスク認識でモデルを拡張するためのフレームワークであるcapsaを紹介します。
  論文  参考訳（メタデータ） (2023-08-01T02:07:47Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。 我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。 この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
  論文  参考訳（メタデータ） (2023-01-19T18:24:08Z)
• Risk-Aware Linear Bandits: Theory and Applications in Smart Order Routing [10.69955834942979]
  スマート・オーダー・ルーティング(SOR)におけるリスク・アウェア・バンディットの最適化について検討する。 分散最小化グローバル最適化(G-Optimal)設計により、新しいインスタンス非依存型リスク意識探索-then-Commit(RISE)アルゴリズムとインスタンス依存型リスク意識継承排除(RISE++)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-04T00:21:10Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  決定推定係数は, 相手の意思決定に対する後悔度を低く抑えるのに必要であり, 十分であることを示す。 我々は、決定推定係数を他のよく知られた複雑性尺度の変種に結びつける新しい構造結果を提供する。
  論文  参考訳（メタデータ） (2022-06-27T06:20:37Z)
• Transfer Learning in Bandits with Latent Continuity [16.60101598919283]
  本稿では,エージェントが先行タスクから次のタスクへ構造情報を転送することを学習しなければならない伝達学習環境について考察する。 本稿では,従来の課題に基づいて,リプシッツ定数を証明的かつ正確に推定する新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2021-02-04T08:19:12Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes [53.72166325215299]
  エピソード因子化マルコフ決定過程(FMDP)における最小強化学習について検討する。 第一に、分解された構造のリッチなクラスに対する最小限の後悔の保証を達成する。 2つ目は、少し悪い後悔をしながら、より良い計算複雑性を楽しみます。
  論文  参考訳（メタデータ） (2020-06-24T00:50:17Z)
• A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
  両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。 本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-23T19:52:44Z)

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

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