論文の概要: Dynamical Linear Bandits
- arxiv url: http://arxiv.org/abs/2211.08997v2
- Date: Tue, 30 May 2023 10:17:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 02:18:28.244314
- Title: Dynamical Linear Bandits
- Title（参考訳）: 動的線形バンディット
- Authors: Marco Mussi, Alberto Maria Metelli and Marcello Restelli
- Abstract要約: 多くの実世界のシーケンシャルな意思決定問題において、アクションはすぐにフィードバックを反映せず、その効果を長い時間枠で広げる。
これまでの研究は、遅延や集約されたフィードバックの可能性について、Multi-Armed Banditフレームワークを調査してきた。
本稿では,隠れ状態に特徴付けられる線形帯域の拡張である動的線形帯域(DLB)について紹介する。
- 参考スコア（独自算出の注目度）: 45.3190496371625
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In many real-world sequential decision-making problems, an action does not
immediately reflect on the feedback and spreads its effects over a long time
frame. For instance, in online advertising, investing in a platform produces an
instantaneous increase of awareness, but the actual reward, i.e., a conversion,
might occur far in the future. Furthermore, whether a conversion takes place
depends on: how fast the awareness grows, its vanishing effects, and the
synergy or interference with other advertising platforms. Previous work has
investigated the Multi-Armed Bandit framework with the possibility of delayed
and aggregated feedback, without a particular structure on how an action
propagates in the future, disregarding possible dynamical effects. In this
paper, we introduce a novel setting, the Dynamical Linear Bandits (DLB), an
extension of the linear bandits characterized by a hidden state. When an action
is performed, the learner observes a noisy reward whose mean is a linear
function of the hidden state and of the action. Then, the hidden state evolves
according to linear dynamics, affected by the performed action too. We start by
introducing the setting, discussing the notion of optimal policy, and deriving
an expected regret lower bound. Then, we provide an optimistic regret
minimization algorithm, Dynamical Linear Upper Confidence Bound (DynLin-UCB),
that suffers an expected regret of order $\widetilde{\mathcal{O}} \Big( \frac{d
\sqrt{T}}{(1-\overline{\rho})^{3/2}} \Big)$, where $\overline{\rho}$ is a
measure of the stability of the system, and $d$ is the dimension of the action
vector. Finally, we conduct a numerical validation on a synthetic environment
and on real-world data to show the effectiveness of DynLin-UCB in comparison
with several baselines.
- Abstract（参考訳）: 多くの実世界のシーケンシャルな意思決定問題において、アクションはすぐにフィードバックを反映せず、その効果を長い時間枠で広げる。
例えば、オンライン広告では、プラットフォームへの投資は瞬時に認知の増大をもたらすが、実際の報酬、すなわち変換は将来的にははるかに起こるかもしれない。
さらに、変換が行われるかどうかは、認知度がどの程度速くなり、その消失効果、他の広告プラットフォームとのシナジーや干渉などに依存する。
前回の研究では、アクションが将来どのように伝播するかという特定の構造がなく、動的効果を無視して、遅延フィードバックと集約フィードバックの可能性を伴って、マルチアームのバンディットフレームワークを調査した。
本稿では,隠れ状態に特徴付けられる線形帯域の拡張である動的線形帯域(DLB)について紹介する。
アクションが実行されると、学習者は、平均が隠れた状態と動作の線形関数であるうるさい報酬を観察する。
そして、隠れた状態は線形ダイナミクスに従って進化し、実行されたアクションにも影響される。
まず、設定を導入し、最適政策の概念を議論し、期待された後悔の限界を導出することから始める。
次に、楽観的な後悔の最小化アルゴリズムdynlin-ucb(dynamical linear upper confidence bound)を提供し、それは$\widetilde{\mathcal{o}} \big( \frac{d \sqrt{t}}{(1-\overline{\rho})^{3/2}} \big)$であり、ここで$\overline{\rho}$はシステムの安定性の尺度であり、$d$はアクションベクトルの次元である。
最後に,DynLin-UCBの有効性を示すために,合成環境と実世界のデータを用いた数値検証を行った。
関連論文リスト
- Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。
本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。
我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
論文 参考訳（メタデータ） (2024-11-05T13:55:52Z) - Bidirectional Decoding: Improving Action Chunking via Closed-Loop Resampling [51.38330727868982]
双方向デコーディング(BID)は、クローズドループ操作で動作チャンキングをブリッジするテスト時間推論アルゴリズムである。
BIDは、7つのシミュレーションベンチマークと2つの実世界のタスクにまたがって、最先端の2つの生成ポリシーの性能を向上させることを示す。
論文 参考訳（メタデータ） (2024-08-30T15:39:34Z) - Sparsity-Agnostic Linear Bandits with Adaptive Adversaries [19.84322270472381]
本研究では,各ラウンドにおいて,学習者が要素を選択して報酬を得る一連の行動(特徴ベクトル)を受信する線形帯域について検討する。
期待される報酬は、選択されたアクションの固定だが未知の線形関数である。
線形報酬関数の非ゼロ係数数$S$に依存するスパース後悔境界について検討する。
論文 参考訳（メタデータ） (2024-06-03T10:54:58Z) - Leveraging Offline Data in Linear Latent Bandits [16.006405951752903]
我々は、$textitevery$ exchangeable and coherent stateless decision process is a latent bandit.
本稿では,この部分空間を短いオフライン軌道から保証付きで学習する方法を提案する。
LOCAL-UCBとProBALL-UCBの2つの方法を提案する。
論文 参考訳（メタデータ） (2024-05-27T16:23:34Z) - Last Switch Dependent Bandits with Monotone Payoff Functions [8.860629791560198]
我々は、LSDバンディット計画の近似性、すなわち、最適なアーム推進戦略を演算する(NP-hard)問題を理解するための一歩を踏み出した。
特に、この問題に対する最初の効率的な定数近似アルゴリズムを設計し、自然単調性仮定の下では、その近似が最先端にほぼ一致することを示す。
われわれは,新しい高次元緩和法や仮想状態の進化を反映する技術など,このような問題に対する新たなツールと洞察を開発する。
論文 参考訳（メタデータ） (2023-06-01T04:38:32Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Exploration in Linear Bandits with Rich Action Sets and its Implications
for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。
本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文 参考訳（メタデータ） (2022-07-23T20:25:07Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳（メタデータ） (2021-01-31T16:49:07Z) - Online Sparse Reinforcement Learning [60.44832065993122]
固定地平線, スパース線形決定過程(MDP)におけるオンライン強化学習の難しさについて検討する。
この場合、よく条件付きデータを収集するポリシーが存在するとしても、線形後悔は一般的に避けられないことを示す。
このことは、大規模な行動において、学習の難しさは、優れた探索政策を見つけるのが困難であることに起因していることを示している。
論文 参考訳（メタデータ） (2020-11-08T16:47:42Z) - Nonstationary Reinforcement Learning with Linear Function Approximation [19.521419943509784]
ドリフト環境下での線形関数近似によるマルコフ決定過程(MDP)における強化学習について考察する。
まず、周期的再起動を伴う最小二乗値の楽観的な修正を開発し、変動予算が分かっている場合にその動的後悔を束縛する。
非定常線型 MDP に対する最初の minimax dynamic regret lower bound を導出し、副生成物として Jin らによって未解決の線型 MDP に対する minimax regret lower bound を定めている。
論文 参考訳（メタデータ） (2020-10-08T20:07:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。