論文の概要: Online Markov Decision Processes with Aggregate Bandit Feedback
- arxiv url: http://arxiv.org/abs/2102.00490v1
- Date: Sun, 31 Jan 2021 16:49:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-02 16:08:31.576129
- Title: Online Markov Decision Processes with Aggregate Bandit Feedback
- Title（参考訳）: Aggregate Bandit Feedbackを用いたオンラインマルコフ決定プロセス
- Authors: Alon Cohen, Haim Kaplan, Tomer Koren, Yishay Mansour
- Abstract要約: 本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
- 参考スコア（独自算出の注目度）: 74.85532145498742
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a novel variant of online finite-horizon Markov Decision Processes
with adversarially changing loss functions and initially unknown dynamics. In
each episode, the learner suffers the loss accumulated along the trajectory
realized by the policy chosen for the episode, and observes aggregate bandit
feedback: the trajectory is revealed along with the cumulative loss suffered,
rather than the individual losses encountered along the trajectory. Our main
result is a computationally efficient algorithm with $O(\sqrt{K})$ regret for
this setting, where $K$ is the number of episodes.
We establish this result via an efficient reduction to a novel bandit
learning setting we call Distorted Linear Bandits (DLB), which is a variant of
bandit linear optimization where actions chosen by the learner are
adversarially distorted before they are committed. We then develop a
computationally-efficient online algorithm for DLB for which we prove an
$O(\sqrt{T})$ regret bound, where $T$ is the number of time steps. Our
algorithm is based on online mirror descent with a self-concordant barrier
regularization that employs a novel increasing learning rate schedule.
- Abstract（参考訳）: 可逆的に変化する損失関数と当初未知のダイナミクスを持つオンライン有限ホリゾンマルコフ決定過程の新しい変種を研究する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌跡に沿って蓄積された損失を経験し、総括的盗聴フィードバックを観察する:この軌跡は、軌跡に沿って遭遇する個人的損失よりも、累積的損失とともに明らかにされる。
我々の主な結果は計算効率のよいアルゴリズムで、$O(\sqrt{K})$ regret for this set, where $K$ is the number of episodes。
この結果は,学習者が選択した動作がコミット前に逆向きに歪むような帯域線形最適化の変種であるDistted Linear Bandits (DLB) と呼ばれる新しい帯域線形学習環境に効率よく還元することで実現される。
次に、 DLB の計算効率の高いオンラインアルゴリズムを開発し、$O(\sqrt{T})$ 後悔境界を証明し、$T$ は時間ステップの数です。
我々のアルゴリズムは,新たな学習率のスケジュールを取り入れた自己一致障壁正規化によるオンラインミラー降下に基づく。
関連論文リスト
- In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminates [10.438810967483438]
逆強化学習(IRL)は報酬関数とそれに対応するポリシーを学習することを目的としている。
現在のIRLの作業は、学習するために少なくとも1つの完全な軌跡を集めるのを待つ必要があるため、進行中の軌跡から漸進的に学習することはできない。
本稿では,現在進行中の軌跡の初期状態対を観察しながら,報酬関数と対応する政策を学習する問題について考察する。
論文 参考訳（メタデータ） (2024-10-21T03:16:32Z) - Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret [10.700891331004799]
本稿では,非損失関数を用いた分散オンライン帯域最適化問題について検討する。
プレイヤーは敵を選択し、そのプレイヤーに任意の非線形損失関数を割り当てる。
予想されるアルゴリズムの後悔は、2点偏差を用いた既存のアルゴリズムに匹敵する。
論文 参考訳（メタデータ） (2024-09-24T02:37:33Z) - Online Reinforcement Learning in Markov Decision Process Using Linear
Programming [1.0878040851638]
マルコフ決定過程(MDP)におけるオンライン強化学習について検討した。
我々は,高い確率で$widetildeO(LXsqrtTA)$ regretを実現する,シンプルで効率的なモデルベースアルゴリズムを考案した。
論文 参考訳（メタデータ） (2023-03-31T22:21:41Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Online Prediction in Sub-linear Space [15.773280101995676]
我々は、専門家のアドバイスによるオンライン学習のための最初のサブ線形空間とサブ線形後悔アルゴリズムを提供する。
また,任意の線形後悔アルゴリズムの線形メモリ下限を適応的逆数に対して証明することにより,(強い)適応的逆数と難解な逆数との分離を実証する。
論文 参考訳（メタデータ） (2022-07-16T16:15:39Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。
楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。
我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
論文 参考訳（メタデータ） (2021-10-21T15:25:15Z) - Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究
OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。
我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
論文 参考訳（メタデータ） (2020-10-24T11:02:45Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。