論文の概要: Multi-Armed Bandits with Abstention
- arxiv url: http://arxiv.org/abs/2402.15127v1
- Date: Fri, 23 Feb 2024 06:27:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-26 15:29:35.729741
- Title: Multi-Armed Bandits with Abstention
- Title(参考訳): 留置用多関節バンド
- Authors: Junwen Yang, Tianyuan Jin, Vincent Y. F. Tan
- Abstract要約: 本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
- 参考スコア(独自算出の注目度): 62.749500564313834
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a novel extension of the canonical multi-armed bandit problem
that incorporates an additional strategic element: abstention. In this enhanced
framework, the agent is not only tasked with selecting an arm at each time
step, but also has the option to abstain from accepting the stochastic
instantaneous reward before observing it. When opting for abstention, the agent
either suffers a fixed regret or gains a guaranteed reward. Given this added
layer of complexity, we ask whether we can develop efficient algorithms that
are both asymptotically and minimax optimal. We answer this question
affirmatively by designing and analyzing algorithms whose regrets meet their
corresponding information-theoretic lower bounds. Our results offer valuable
quantitative insights into the benefits of the abstention option, laying the
groundwork for further exploration in other online decision-making problems
with such an option. Numerical results further corroborate our theoretical
findings.
- Abstract(参考訳): 我々は,新たな戦略要素を組み込んだ,正準多武装バンディット問題の新たな拡張を提案する。
この強化されたフレームワークでは、エージェントは各時間ステップでアームを選択することだけでなく、観察する前に確率的な瞬間的な報酬を受け取ることを拒否するオプションを持っている。
棄権を選択した場合、エージェントは一定の後悔に苦しむか、保証された報酬を得る。
この付加的な複雑性層を考えると、漸近的かつミニマックス最適である効率的なアルゴリズムを開発できるかどうかを問う。
我々は,後悔が対応する情報理論下限を満たすアルゴリズムを設計・分析することで,この疑問に肯定的に答える。
以上の結果から,提案オプションのメリットを定量的に把握し,他のオンライン意思決定問題へのさらなる探究の基盤となるものと考えられる。
数値的な結果は我々の理論的な結果をさらに裏付ける。
関連論文リスト
- Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳(メタデータ) (2023-08-29T18:18:21Z) - Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When
Partial Feedback Counts [53.579515853222986]
時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。
この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。
本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-01T15:56:59Z) - Break your Bandit Routine with LSD Rewards: a Last Switch Dependent
Analysis of Satiation and Seasonality [6.146046338698175]
そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。
我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。
我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
論文 参考訳(メタデータ) (2021-10-22T14:53:13Z) - Asymptotic Optimality for Decentralised Bandits [7.057937612386993]
多数の武器で盗賊問題に協力するエージェントを多数検討する。
目標は、コミュニケーション制約のある環境で各エージェントの後悔を最小限にすることである。
論文 参考訳(メタデータ) (2021-09-20T11:10:10Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous
Feedback [32.62857394584907]
複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。
本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-13T12:25:41Z) - Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。
我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。
最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
論文 参考訳(メタデータ) (2020-12-07T08:23:08Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - A Farewell to Arms: Sequential Reward Maximization on a Budget with a
Giving Up Option [5.1629297054995265]
エージェントが一度にひとつのアクションを採り、各アクションが時間的範囲を持つような、シーケンシャルな意思決定問題を考える。
我々は、対数的、問題依存的後悔境界を確立する上で、高い信頼度に基づくアルゴリズム(WAIT-UCB)を導入する。
論文 参考訳(メタデータ) (2020-03-06T22:16:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。