論文の概要: Dynamic Planning and Learning under Recovering Rewards
- arxiv url: http://arxiv.org/abs/2106.14813v1
- Date: Mon, 28 Jun 2021 15:40:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-29 13:49:47.911277
- Title: Dynamic Planning and Learning under Recovering Rewards
- Title（参考訳）: Recovering Rewardsにおける動的計画と学習
- Authors: David Simchi-Levi, Zeyu Zheng, Feng Zhu
- Abstract要約: 我々は「純粋周期ポリシー」のクラスの性能保証を提案し、構築し、証明する。
私たちのフレームワークとポリシー設計は、他のオフライン計画およびオンライン学習アプリケーションに適応する可能性がある。
- 参考スコア（独自算出の注目度）: 18.829837839926956
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by emerging applications such as live-streaming e-commerce,
promotions and recommendations, we introduce a general class of multi-armed
bandit problems that have the following two features: (i) the decision maker
can pull and collect rewards from at most $K$ out of $N$ different arms in each
time period; (ii) the expected reward of an arm immediately drops after it is
pulled, and then non parametrically recovers as the idle time increases. With
the objective of maximizing expected cumulative rewards over $T$ time periods,
we propose, construct and prove performance guarantees for a class of "Purely
Periodic Policies". For the offline problem when all model parameters are
known, our proposed policy obtains an approximation ratio that is at the order
of $1-\mathcal O(1/\sqrt{K})$, which is asymptotically optimal when $K$ grows
to infinity. For the online problem when the model parameters are unknown and
need to be learned, we design an Upper Confidence Bound (UCB) based policy that
approximately has $\widetilde{\mathcal O}(N\sqrt{T})$ regret against the
offline benchmark. Our framework and policy design may have the potential to be
adapted into other offline planning and online learning applications with
non-stationary and recovering rewards.
- Abstract（参考訳）: ライブ配信のeコマースやプロモーション,レコメンデーションなどの新興アプリケーションに動機付けられ,次の2つの特徴を持つマルチアームバンディットの一般的なクラスを導入する。 (i) 意思決定者は,各期間中に最大$K$から$N$の異なる武器から報酬を回収することができ, (ii) 腕の期待報酬は, 引いた後にすぐに低下し, アイドル時間が増加するにつれて非パラメトリックに回復する。
予測累積報酬をT$以上の期間で最大化する目的で,我々は「純粋周期ポリシー」のクラスの性能保証を提案し,構築し,証明する。
すべてのモデルパラメータが知られている場合のオフライン問題に対して、提案手法は1-\mathcal o(1/\sqrt{k})$の順の近似比を得る。
モデルパラメータが不明で学習が必要なオンライン問題に対して、オフラインベンチマークに対して約$\widetilde{\mathcal O}(N\sqrt{T})$後悔するアッパー信頼境界(UCB)ベースのポリシーを設計する。
当社のフレームワークとポリシ設計は,オフライン計画やオンライン学習アプリケーションに,非定常的かつ回復的な報酬を付与する可能性を持ったものです。
関連論文リスト
- Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
後悔は$Thetaleft(mfrac12cdotfrac11-2-Tright)$で半直線的に成長するので、指数関数的に$Theta(sqrtm)$に収束する。
これらの調査結果は、限定的なオンライン学習と最適化の利点を浮き彫りにしている。
論文 参考訳（メタデータ） (2024-06-20T23:00:25Z) - Online Policy Learning and Inference by Matrix Completion [12.527541242185404]
行列完備帯域(MCB)として問題を定式化する。
我々は、$epsilon$-greedy banditとオンライン勾配降下について検討する。
より早く崩壊する探索は、より少ない後悔をもたらすが、最適なポリシーをより正確に学習する。
論文 参考訳（メタデータ） (2024-04-26T13:19:27Z) - Online Resource Allocation in Episodic Markov Decision Processes [1.8416014644193066]
本稿では, 有限水平制約マルコフ決定過程におけるオンライン割当問題として, 問題を定式化する。
本稿では,観測・観測・観測・観測体制の整備と既存の決定・観測体制の改善について述べる。
平均報酬と平均資源消費関数にアクセスできる静的最適政策に対する後悔は、高い確率で$tilde O(rho-1H3/2SsqrtAT)$で束縛されていることを示す。
論文 参考訳（メタデータ） (2023-05-18T06:28:34Z) - 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) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-13T19:11:22Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳（メタデータ） (2022-02-28T12:10:48Z) - PDE-Based Optimal Strategy for Unconstrained Online Learning [40.61498562988079]
部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。
我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。
これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
論文 参考訳（メタデータ） (2022-01-19T22:21:21Z) - Provably Efficient Generative Adversarial Imitation Learning for Online
and Offline Setting with Linear Function Approximation [81.0955457177017]
GAIL(Generative Adversarial mimicion Learning)では、特定の報酬セットにおいて、専門家の政策からそのパフォーマンスを区別できないように、専門家のデモンストレーションからポリシーを学習することを目的としている。
GAILをオンラインとオフラインの両方で線形関数近似を用いて検討し、その変換関数と報酬関数は特徴写像において線形である。
論文 参考訳（メタデータ） (2021-08-19T16:16:00Z) - Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation
for Reinforcement Learning [43.61029925616256]
強化学習(RL)におけるオフラインポリシー評価は、実生活アプリケーションにRLを適用するための重要なステップである。
ポリシクラス$Pi$ -- OPEの統一収束を同時に評価することで、この問題に対処する。
以上の結果から,モデルベースプランニングにより,$widetildeO(H3/d_mepsilon2)$の最適なエピソード複雑性を達成できることが示唆された。
論文 参考訳（メタデータ） (2020-07-07T19:44:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。