論文の概要: Dynamic Bandits with an Auto-Regressive Temporal Structure
- arxiv url: http://arxiv.org/abs/2210.16386v1
- Date: Fri, 28 Oct 2022 20:02:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 19:13:42.634196
- Title: Dynamic Bandits with an Auto-Regressive Temporal Structure
- Title(参考訳): 自己回帰型時間構造をもつダイナミックバンド
- Authors: Qinyi Chen, Negin Golrezaei, Djallel Bouneffouf
- Abstract要約: 時間構造を持つ動的マルチアームバンディット(MAB)問題について検討する。
報酬の動的な性質のため、単純な"発見とコミット"ポリシーは失敗する。
約1ラウンドの後悔が我々の後悔の少ない限界にほぼ一致するアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 22.047485313712997
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-armed bandit (MAB) problems are mainly studied under two extreme
settings known as stochastic and adversarial. These two settings, however, do
not capture realistic environments such as search engines and marketing and
advertising, in which rewards stochastically change in time. Motivated by that,
we introduce and study a dynamic MAB problem with stochastic temporal
structure, where the expected reward of each arm is governed by an
auto-regressive (AR) model. Due to the dynamic nature of the rewards, simple
"explore and commit" policies fail, as all arms have to be explored
continuously over time. We formalize this by characterizing a per-round regret
lower bound, where the regret is measured against a strong (dynamic) benchmark.
We then present an algorithm whose per-round regret almost matches our regret
lower bound. Our algorithm relies on two mechanisms: (i) alternating between
recently pulled arms and unpulled arms with potential, and (ii) restarting.
These mechanisms enable the algorithm to dynamically adapt to changes and
discard irrelevant past information at a suitable rate. In numerical studies,
we further demonstrate the strength of our algorithm under different types of
non-stationary settings.
- Abstract(参考訳): マルチアーム・バンディット(MAB)問題は、主に確率と逆数と呼ばれる2つの極端な条件下で研究されている。
しかし、これらの2つの設定は、検索エンジンやマーケティングや広告のような現実的な環境を捉えていない。
そこで我々は,各腕の期待報酬が自己回帰モデル(AR)によって支配される確率的時間構造を持つ動的MAB問題を紹介し,研究する。
報酬の動的な性質のため、単純な「発見とコミット」ポリシーは失敗する。
我々は、このことを、強い(ダイナミックな)ベンチマークに対して後悔を計測する、丸ごとの後悔の低い境界を特徴付けることで、形式化する。
次に、全周的後悔が我々の後悔の低い境界にほぼ一致するアルゴリズムを示す。
アルゴリズムは2つのメカニズムに依存しています
一 最近引き抜かれた腕と潜在的に無力な腕との交互
(ii)再開。
これらのメカニズムにより、アルゴリズムは変化に動的に適応し、不適切な過去の情報を適切な速度で破棄することができる。
数値解析では,異なるタイプの非定常条件下でのアルゴリズムの強みをさらに示す。
関連論文リスト
- GPT-ST: Generative Pre-Training of Spatio-Temporal Graph Neural Networks [24.323017830938394]
この作業は、ベースラインとシームレスに統合し、パフォーマンスを向上する事前トレーニングフレームワークを導入することで、課題に対処することを目的としている。
フレームワークは2つの重要な設計に基づいて構築されている。
Apple-to-appleマスクオートエンコーダは、学習時間依存のための事前トレーニングモデルである。
これらのモジュールは、時間内カスタマイズされた表現とセマンティック・クラスタ間関係を捉えるように設計されている。
論文 参考訳(メタデータ) (2023-11-07T02:36:24Z) - Revisiting the Temporal Modeling in Spatio-Temporal Predictive Learning
under A Unified View [73.73667848619343]
UTEP(Unified S-Temporal Predictive Learning)は,マイクロテンポラリスケールとマクロテンポラリスケールを統合した再帰的および再帰的フリーな手法を再構築する,革新的なフレームワークである。
論文 参考訳(メタデータ) (2023-10-09T16:17:42Z) - Losing momentum in continuous-time stochastic optimisation [62.997667081978825]
近年,運動量に基づくアルゴリズムが特に普及している。
本研究では,運動量を伴う勾配降下の連続時間モデルを提案し,解析する。
我々は、時間とともに運動量を減らす際に、我々のシステムを世界規模のミニミザーに収束させることを示す。
論文 参考訳(メタデータ) (2022-09-08T10:46:05Z) - Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline
Reinforcement Learning [114.36124979578896]
オフライン強化学習アルゴリズムを用いて動的メカニズムを設計する。
我々のアルゴリズムは悲観主義の原理に基づいており、オフラインデータセットのカバレッジについて軽度な仮定しか必要としない。
論文 参考訳(メタデータ) (2022-05-05T05:44:26Z) - Accelerated Continuous-Time Approximate Dynamic Programming via
Data-Assisted Hybrid Control [0.0]
本研究では,アクター・クリティックな構造に動的運動量を組み込んだアルゴリズムを導入し,アフィン構造を入力とする連続時間動植物を制御する。
アルゴリズムに動的運動量を導入することにより、閉ループ系の収束特性を加速することができる。
論文 参考訳(メタデータ) (2022-04-27T05:36:51Z) - Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement
Learning Approach [130.9259586568977]
本稿では,複数ラウンドの対話を通して動的ビックレー・クラーク・グローブ(VCG)機構を回復するための新しい学習アルゴリズムを提案する。
当社のアプローチの重要な貢献は、報酬のないオンライン強化学習(RL)を取り入れて、リッチな政策分野の探索を支援することである。
論文 参考訳(メタデータ) (2022-02-25T16:17:23Z) - Rebounding Bandits for Modeling Satiation Effects [22.92512152419544]
リバウンダリング・バンディット(rebounding bandit)は、時間不変線形力学系として飽和力学をモデル化するマルチアーム・バンディット・セットアップである。
我々は、腕が同一のダイナミクスを示す場合に、欲求政策が最適であることを示す計画問題を特徴づける。
論文 参考訳(メタデータ) (2020-11-13T03:17:29Z) - Stochastically forced ensemble dynamic mode decomposition for
forecasting and analysis of near-periodic systems [65.44033635330604]
本稿では,観測力学を強制線形系としてモデル化した新しい負荷予測手法を提案する。
固有線型力学の利用は、解釈可能性やパーシモニーの観点から、多くの望ましい性質を提供することを示す。
電力グリッドからの負荷データを用いたテストケースの結果が提示される。
論文 参考訳(メタデータ) (2020-10-08T20:25:52Z) - Automated and Formal Synthesis of Neural Barrier Certificates for
Dynamical Models [70.70479436076238]
バリア証明書(BC)の自動的,形式的,反例に基づく合成手法を提案する。
このアプローチは、ニューラルネットワークとして構造化されたBCの候補を操作する誘導的フレームワークと、その候補の有効性を認証するか、反例を生成する音検証器によって支えられている。
その結果,音のBCsを最大2桁の速度で合成できることがわかった。
論文 参考訳(メタデータ) (2020-07-07T07:39:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。