論文の概要: Online Model Selection: a Rested Bandit Formulation
- arxiv url: http://arxiv.org/abs/2012.03522v1
- Date: Mon, 7 Dec 2020 08:23:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-16 21:47:46.777102
- Title: Online Model Selection: a Rested Bandit Formulation
- Title(参考訳): オンラインモデル選択: rested banditの定式化
- Authors: Leonardo Cella and Claudio Gentile and Massimiliano Pontil
- Abstract要約: 静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。
我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。
最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
- 参考スコア(独自算出の注目度): 49.69377391589057
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by a natural problem in online model selection with bandit
information, we introduce and analyze a best arm identification problem in the
rested bandit setting, wherein arm expected losses decrease with the number of
times the arm has been played. The shape of the expected loss functions is
similar across arms, and is assumed to be available up to unknown parameters
that have to be learned on the fly. We define a novel notion of regret for this
problem, where we compare to the policy that always plays the arm having the
smallest expected loss at the end of the game. We analyze an arm elimination
algorithm whose regret vanishes as the time horizon increases. The actual rate
of convergence depends in a detailed way on the postulated functional form of
the expected losses. Unlike known model selection efforts in the recent bandit
literature, our algorithm exploits the specific structure of the problem to
learn the unknown parameters of the expected loss function so as to identify
the best arm as quickly as possible. We complement our analysis with a lower
bound, indicating strengths and limitations of the proposed solution.
- Abstract(参考訳): バンディット情報を用いたオンラインモデル選択における自然問題に触発され,残バンドディット設定における最適な腕識別問題を導入,解析し,腕の再生回数に応じて腕の期待損失が減少する。
期待される損失関数の形状は腕間で似ており、ハエで学ばなければならない未知のパラメータまで利用できると推定されている。
我々はこの問題に対する後悔という新しい概念を定義し、ゲーム終了時に最も期待される損失の少ないアームを常にプレイするポリシーと比較する。
時間軸の増加に伴って後悔が失われるアーム除去アルゴリズムを解析する。
実際の収束速度は、期待される損失の仮定された機能形式に依存する。
最近のバンディット文学における既知のモデル選択の取り組みとは異なり、本アルゴリズムは問題の特定の構造を利用して期待損失関数の未知のパラメータを学習し、最良のアームをできるだけ早く識別する。
我々は,提案手法の強みと限界を示し,より低い境界で解析を補完する。
関連論文リスト
- Contextual Bandits with Arm Request Costs and Delays [19.263086804406786]
本稿では,時間的遅延と関連するコストを伴って,新たなアームセットを要求できるコンテキスト的バンディット問題の拡張を提案する。
この設定では、学習者は、各選択が1つの時間単位を取るように、決定セットから複数のアームを選択することができる。
我々は、武器を効果的に選択し、新しい武器を要求する適切な時間を決定するアルゴリズムを設計し、彼らの後悔を最小限に抑える。
論文 参考訳(メタデータ) (2024-10-17T00:44:50Z) - Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳(メタデータ) (2024-09-27T16:46:02Z) - Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳(メタデータ) (2024-09-09T18:23:07Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳(メタデータ) (2021-05-22T02:46:04Z) - Online Algorithm for Unsupervised Sequential Selection with Contextual
Information [38.47252956961143]
文脈教師なしシーケンス選択(USS)について検討する。
USSは、観測されたフィードバックから腕の喪失を推測できない文脈的包帯問題の新しい変種である。
本稿では,文脈的 USS 問題に対するアルゴリズムを提案し,それがサブ線形後悔であることを示す。
論文 参考訳(メタデータ) (2020-10-23T12:32:21Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-23T19:52:44Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳(メタデータ) (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。