論文の概要: Optimal Learning for Structured Bandits

• arxiv url: http://arxiv.org/abs/2007.07302v3
• Date: Mon, 10 Jul 2023 14:50:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-11 19:52:23.217229
• Title: Optimal Learning for Structured Bandits
• Title（参考訳）: 構造化バンディットの最適学習
• Authors: Bart P.G. Van Parys, Negin Golrezaei
• Abstract要約: 本研究では,構造情報の存在下での不確実性の下でのオンライン意思決定の問題である,構造化されたマルチアームバンディットについて検討する。 本稿では,情報理論的後悔を一定要素まで低く抑え,幅広い構造情報を扱える新しい学習アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 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 convex structural information regarding the reward distributions; that is, the decision-maker knows the reward distributions of the arms belong to a convex compact set. In the presence such structural information, they then 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 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 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. We show that this idea leads to the first computationally viable learning policy with asymptotic minimal regret for various structural information, including well-known structured bandits such as linear, Lipschitz, and convex bandits, and novel structured bandits that have not been studied in the literature due to the lack of a unified and flexible framework.
• 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)

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

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