論文の概要: Delayed Bandits: When Do Intermediate Observations Help?
- arxiv url: http://arxiv.org/abs/2305.19036v1
- Date: Tue, 30 May 2023 13:52:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 16:01:42.615910
- Title: Delayed Bandits: When Do Intermediate Observations Help?
- Title（参考訳）: 遅延帯域: 中間観察はいつ役に立つか?
- Authors: Emmanuel Esposito, Saeed Masoudian, Hao Qiu, Dirk van der Hoeven,
Nicol\`o Cesa-Bianchi, Yevgeny Seldin
- Abstract要約: 我々は,フィードバックの遅れと中間観察を伴って,$Kの武器付きバンディットについて検討した。
状態と損失のマッピングの体制が問題の複雑さを決定づけていることが示される。
- 参考スコア（独自算出の注目度）: 19.13297969651745
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a $K$-armed bandit with delayed feedback and intermediate
observations. We consider a model where intermediate observations have a form
of a finite state, which is observed immediately after taking an action,
whereas the loss is observed after an adversarially chosen delay. We show that
the regime of the mapping of states to losses determines the complexity of the
problem, irrespective of whether the mapping of actions to states is stochastic
or adversarial. If the mapping of states to losses is adversarial, then the
regret rate is of order $\sqrt{(K+d)T}$ (within log factors), where $T$ is the
time horizon and $d$ is a fixed delay. This matches the regret rate of a
$K$-armed bandit with delayed feedback and without intermediate observations,
implying that intermediate observations are not helpful. However, if the
mapping of states to losses is stochastic, we show that the regret grows at a
rate of $\sqrt{\big(K+\min\{|\mathcal{S}|,d\}\big)T}$ (within log factors),
implying that if the number $|\mathcal{S}|$ of states is smaller than the
delay, then intermediate observations help. We also provide refined
high-probability regret upper bounds for non-uniform delays, together with
experimental validation of our algorithms.
- Abstract（参考訳）: 遅延フィードバックと中間観測を伴って,k$-armed banditについて検討した。
本研究では, 中間観測が有限状態の形で, 動作開始直後に観測されるのに対して, 逆選択された遅延後に損失が観測されるモデルを考える。
我々は、状態への対応のマッピングが確率的か逆かにかかわらず、状態から損失へのマッピングの体制が問題の複雑さを決定することを示した。
状態の損失へのマッピングが逆ならば、後悔率は次数$\sqrt{(K+d)T}$(ログ要素なしで)であり、$T$は時間軸、$d$は固定遅延である。
これは、$Kの武器付きバンディットの後悔率と、遅延したフィードバックと中間的な観察がなければ、中間的な観察が役に立たないことを意味する。
しかし、損失への状態のマッピングが確率的であれば、後悔は$\sqrt{\big(k+\min\{|\mathcal{s}|,d\}\big)t}$(対数係数を含む)の割合で増加することが示され、もし$|\mathcal{s}|$の状態が遅延よりも小さいなら、中間観測は助けとなる。
また,非一様遅延に対する高確率後悔上限と,アルゴリズムの実験的検証も提供する。
関連論文リスト
- Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
論文 参考訳（メタデータ） (2024-02-14T13:08:26Z) - Efficient Reinforcement Learning with Impaired Observability: Learning
to Act with Delayed and Missing State Observations [92.25604137490168]
本稿では,制御系における効率的な強化学習に関する理論的研究を紹介する。
遅延および欠落した観測条件において,RL に対して $tildemathcalO(sqrtrm poly(H) SAK)$ という形でアルゴリズムを提示し,その上限と下限をほぼ最適に設定する。
論文 参考訳（メタデータ） (2023-06-02T02:46:39Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳（メタデータ） (2023-05-25T14:02:12Z) - Reinforcement Learning with Delayed, Composite, and Partially Anonymous
Reward [41.61653528766776]
無限水平平均報酬マルコフ決定過程 (MDP) を, 遅延, 複合, 部分的に匿名の報酬フィードバックを用いて検討した。
報酬の遅延と合成性は、与えられた状態におけるアクションの結果として生成された報酬を、異なるコンポーネントに分割することを意味する。
論文 参考訳（メタデータ） (2023-05-04T03:31:30Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳（メタデータ） (2022-03-18T08:03:20Z) - Learning Adversarial Markov Decision Processes with Delayed Feedback [45.86354980347581]
私たちは、未知の移行、逆転的なコストの変動、制限のない遅延フィードバックを備えた典型的マルコフ決定プロセス(MDP)におけるオンライン学習を検討します。
本論文では,$widetilde O ( sqrtK + sqrtD )$ のほぼ最適高確率後悔を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-29T16:47:42Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳（メタデータ） (2020-10-12T20:53:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。