論文の概要: Worst-case Performance of Greedy Policies in Bandits with Imperfect
Context Observations
- arxiv url: http://arxiv.org/abs/2204.04773v1
- Date: Sun, 10 Apr 2022 21:27:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-12 14:27:11.408909
- Title: Worst-case Performance of Greedy Policies in Bandits with Imperfect
Context Observations
- Title(参考訳): 不完全観測帯域におけるグリーディ政策の最悪の性能
- Authors: Hongju Park and Mohamad Kazem Shirani Faradonbeh
- Abstract要約: この研究は、パラメータと観測されていないコンテキストの現在の推定値が対応する真の値と一致するかのように行動をとるグレディ強化学習ポリシーを考察する。
非漸近的な最悪の後悔は、時間軸や失敗確率と対数的に増大する一方、腕の数と線形にスケールする。
- 参考スコア(独自算出の注目度): 1.370633147306388
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Contextual bandits are canonical models for sequential decision-making under
uncertainty in environments with time-varying components. In this setting, the
expected reward of each bandit arm consists of the inner product of an unknown
parameter and the context vector of that arm, perturbed with a random error.
The classical setting heavily relies on fully observed contexts, while study of
the richer model of imperfectly observed contextual bandits is immature. This
work considers Greedy reinforcement learning policies that take actions as if
the current estimates of the parameter and of the unobserved contexts coincide
with the corresponding true values. We establish that the non-asymptotic
worst-case regret grows logarithmically with the time horizon and the failure
probability, while it scales linearly with the number of arms. Numerical
analysis showcasing the above efficiency of Greedy policies is also provided.
- Abstract(参考訳): 文脈帯域は、時間変化成分を持つ環境における不確実性の下での逐次決定のための標準モデルである。
この設定では、各バンディットアームの期待される報酬は、未知のパラメータの内部積と、そのアームのコンテキストベクトルからなり、ランダムな誤差で摂動する。
古典的設定は、完全に観察された文脈に大きく依存するが、不完全に観察された文脈的バンディットのよりリッチなモデルの研究は未熟である。
この研究は、パラメータと観測されていないコンテキストの現在の推定値が対応する真の値と一致するかのように行動をとるグレディ強化学習ポリシーを考察する。
非漸近的な最悪の後悔は、時間軸や失敗確率と対数的に増大する一方、腕の数と線形にスケールする。
以上のグリーディ政策の効率を示す数値解析も提供する。
関連論文リスト
- Thompson Sampling in Partially Observable Contextual Bandits [2.465689259704613]
我々は、観測データに基づいて最適な腕を選択することを学ぶための盗賊政策について研究する。
我々の理論的分析は、トンプソンサンプリング政策が探索と搾取のバランスをうまくとれることを示している。
これらの技術は、文脈情報や部分的な観察とともに、他の意思決定問題の研究への道を開く。
論文 参考訳(メタデータ) (2024-02-15T19:37:39Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - Online learning in bandits with predicted context [9.280355951055865]
エージェントがコンテキストの騒々しいバージョンにしかアクセスできない場合、コンテキスト的帯域幅の問題を考える。
この設定は、意思決定の真のコンテキストが守られない広範囲のアプリケーションによって動機付けられている。
本研究では,この設定において,軽度条件下でのサブ線形後悔保証を用いた最初のオンラインアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-07-26T02:33:54Z) - A Unified Framework of Policy Learning for Contextual Bandit with
Confounding Bias and Missing Observations [108.89353070722497]
本研究では,観測データを用いた最適ポリシの獲得を目的とした,オフラインのコンテキスト的帯域幅問題について検討する。
本稿では、積分方程式系の解として報酬関数を形成するCausal-Adjusted Pessimistic(CAP)ポリシー学習という新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-20T15:17:31Z) - Reproducible Bandits [95.8830340560603]
バンディット環境におけるポリシーは、2つの異なる実行において全く同じ腕列を高い確率で引き出すと再現可能と呼ばれる。
再現可能なポリシが存在するだけでなく、時間的地平線の観点から、ほぼ同じ(再現不可能な)後悔境界を達成することを示す。
以上の結果から,無作為化が探索・探索トレードオフに不可欠であるにもかかわらず,同一の腕を2回の異なるラウンドで引き抜いて最適なバランスをとれることが示唆された。
論文 参考訳(メタデータ) (2022-10-04T20:36:45Z) - Analysis of Thompson Sampling for Partially Observable Contextual
Multi-Armed Bandits [1.8275108630751844]
我々は、部分的に観測可能なコンテキスト多重武装バンディットのためのトンプソンサンプリングアルゴリズムを提案する。
提示された政策の後悔は、時間と武器の数に応じて対数的にスケールし、寸法と直線的にスケールすることを示す。
論文 参考訳(メタデータ) (2021-10-23T08:51:49Z) - Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。
我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。
最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
論文 参考訳(メタデータ) (2020-12-07T08:23:08Z) - Greedy Bandits with Sampled Context [0.0]
Greedy Bandits with Sampled Context (GB-SC) は、コンテキスト情報から事前の開発を行うためのコンテキスト多重武装バンディットの手法である。
以上の結果から,Mushroom環境において,期待される後悔と期待される累積的後悔の両面での競争性能が示された。
論文 参考訳(メタデータ) (2020-07-27T17:17:45Z) - Offline Contextual Bandits with Overparameterized Models [52.788628474552276]
オフラインの文脈的盗賊にも同じ現象が起こるかどうかを問う。
この相違は, 目的の強調安定性によるものであることを示す。
大規模なニューラルネットワークを用いた実験では、アクション安定な値ベース目標と不安定なポリシベース目標とのギャップは、大きなパフォーマンス差をもたらす。
論文 参考訳(メタデータ) (2020-06-27T13:52:07Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳(メタデータ) (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。