論文の概要: Break your Bandit Routine with LSD Rewards: a Last Switch Dependent Analysis of Satiation and Seasonality

• arxiv url: http://arxiv.org/abs/2110.11819v1
• Date: Fri, 22 Oct 2021 14:53:13 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-25 15:33:15.374969
• Title: Break your Bandit Routine with LSD Rewards: a Last Switch Dependent Analysis of Satiation and Seasonality
• Title（参考訳）: LSD Rewards によるバンドルーチンの切断:最後のスイッチ依存による満足度と季節性の分析
• Authors: Pierre Laforgue, Giulia Clerici, Nicol\`o Cesa-Bianchi, Ran Gilad-Bachrach
• Abstract要約: そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。 我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。 我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
• 参考スコア（独自算出の注目度）: 6.146046338698175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the fact that humans like some level of unpredictability or novelty, and might therefore get quickly bored when interacting with a stationary policy, we introduce a novel non-stationary bandit problem, where the expected reward of an arm is fully determined by the time elapsed since the arm last took part in a switch of actions. Our model generalizes previous notions of delay-dependent rewards, and also relaxes most assumptions on the reward function. This enables the modeling of phenomena such as progressive satiation and periodic behaviours. Building upon the Combinatorial Semi-Bandits (CSB) framework, we design an algorithm and prove a bound on its regret with respect to the optimal non-stationary policy (which is NP-hard to compute). Similarly to previous works, our regret analysis is based on defining and solving an appropriate trade-off between approximation and estimation. Preliminary experiments confirm the superiority of our algorithm over both the oracle greedy approach and a vanilla CSB solver.
• Abstract（参考訳）: 人間は何らかの予測不可能さや新奇さを好んでおり、定常的な政策と対話するときにすぐに退屈するかもしれないという事実に感銘を受け、我々は、腕の期待される報酬が、最後に行動の切り替えに参加した時から経過した時間によって完全に決定される、新しい非定常的盗賊問題を導入する。 我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。 これにより、進行的な満足や周期的な振る舞いのような現象のモデリングが可能になる。 CSB( Combinatorial Semi-Bandits)フレームワークを基盤として,アルゴリズムを設計し,最適な非定常ポリシー(NP-hard to compute)に関して,その後悔を証明している。 過去の研究と同様に、我々の後悔の分析は近似と推定の間の適切なトレードオフを定義し、解決することに基づいている。 予備実験により,oracle greedy アプローチと vanilla csb ソルバに対するアルゴリズムの優位性を確認した。

関連論文リスト

• Multi-Armed Bandits with Abstention [62.749500564313834]
  本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。 この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
  論文  参考訳（メタデータ） (2024-02-23T06:27:12Z)
• Last Switch Dependent Bandits with Monotone Payoff Functions [8.860629791560198]
  我々は、LSDバンディット計画の近似性、すなわち、最適なアーム推進戦略を演算する(NP-hard)問題を理解するための一歩を踏み出した。 特に、この問題に対する最初の効率的な定数近似アルゴリズムを設計し、自然単調性仮定の下では、その近似が最先端にほぼ一致することを示す。 われわれは,新しい高次元緩和法や仮想状態の進化を反映する技術など,このような問題に対する新たなツールと洞察を開発する。
  論文  参考訳（メタデータ） (2023-06-01T04:38:32Z)
• Reward Imputation with Sketching for Contextual Batched Bandits [48.80803376405073]
  コンテキストバッチバンドイット(Contextual batched bandit、CBB)は、各エピソードの最後に環境から報酬のバッチを観測する設定である。 CBBの既存のアプローチは、実行されていないアクションの報酬を無視し、フィードバック情報の未利用につながることが多い。 本研究では,未観測の報酬をスケッチを用いて完遂するSketched Policy Updating with Imputed Rewards (SPUIR)を提案する。
  論文  参考訳（メタデータ） (2022-10-13T04:26:06Z)
• 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)
• Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
  最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。 本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。 我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。 腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
  論文  参考訳（メタデータ） (2021-05-22T02:46:04Z)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• A Farewell to Arms: Sequential Reward Maximization on a Budget with a Giving Up Option [5.1629297054995265]
  エージェントが一度にひとつのアクションを採り、各アクションが時間的範囲を持つような、シーケンシャルな意思決定問題を考える。 我々は、対数的、問題依存的後悔境界を確立する上で、高い信頼度に基づくアルゴリズム(WAIT-UCB)を導入する。
  論文  参考訳（メタデータ） (2020-03-06T22:16:20Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。 我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
  論文  参考訳（メタデータ） (2020-02-19T15:41:18Z)
• A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
  本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。 予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。 SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-02-12T18:54:41Z)

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

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