論文の概要: Online Decision Making with History-Average Dependent Costs (Extended)
- arxiv url: http://arxiv.org/abs/2312.06641v1
- Date: Mon, 11 Dec 2023 18:55:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-12 14:21:48.560731
- Title: Online Decision Making with History-Average Dependent Costs (Extended)
- Title(参考訳): 履歴平均依存コストによるオンライン意思決定(拡張)
- Authors: Vijeth Hebbar and Cedric Langbort
- Abstract要約: 多くのオンライン意思決定シナリオにおいて、学習者の選択は現在のコストだけでなく将来のコストにも影響を及ぼす。
まず、段階的な制約の下での意思決定の問題として、歴史依存のコストでこの問題を再考する。
次に,Follow-The-Adaptively-Regularized-Leader (FTARL)アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.29008108937701327
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In many online sequential decision-making scenarios, a learner's choices
affect not just their current costs but also the future ones. In this work, we
look at one particular case of such a situation where the costs depend on the
time average of past decisions over a history horizon. We first recast this
problem with history dependent costs as a problem of decision making under
stage-wise constraints. To tackle this, we then propose the novel
Follow-The-Adaptively-Regularized-Leader (FTARL) algorithm. Our innovative
algorithm incorporates adaptive regularizers that depend explicitly on past
decisions, allowing us to enforce stage-wise constraints while simultaneously
enabling us to establish tight regret bounds. We also discuss the implications
of the length of history horizon on design of no-regret algorithms for our
problem and present impossibility results when it is the full learning horizon.
- Abstract(参考訳): 多くのオンライン意思決定シナリオにおいて、学習者の選択は現在のコストだけでなく将来のコストにも影響を及ぼす。
本研究は,過去の意思決定の時間平均に依存したコストが歴史の地平線に掛かる状況の特殊な事例を考察する。
まず,段階的な制約下での意思決定問題として,歴史依存コストを用いてこの問題を再キャストした。
そこで本研究では,適応正規化リード (ftarl) アルゴリズムを提案する。
我々の革新的なアルゴリズムは、過去の決定に明示的に依存する適応正規化器を組み込んでおり、段階的な制約を課すと同時に、厳密な後悔の境界を確立することができる。
また,歴史の地平線の長さが問題に対する非regretアルゴリズムの設計に与える影響についても考察し,それが完全な学習地平線である場合に不確実性を示す。
関連論文リスト
- Playing in the Dark: No-regret Learning with Adversarial Constraints [20.077237398506536]
本稿では,従来のオンライン凸最適化(OCO)フレームワークの長期的制約を考慮した一般化について検討する。
我々は,任意のOCOポリシを用いて代理問題を解くことで,最適な性能境界を実現することができることを示す。
新たなリャプノフに基づく証明手法が提示され、後悔と特定の逐次不等式の間の関係を明らかにする。
論文 参考訳(メタデータ) (2023-10-29T09:55:41Z) - Online Learning with Costly Features in Non-stationary Environments [6.009759445555003]
シーケンシャルな意思決定の問題では、長期的な報酬を最大化することが第一の目標である。
現実世界の問題では、有益な情報を集めるのにしばしばコストがかかる。
時間内にサブ線形後悔を保証するアルゴリズムを開発する。
論文 参考訳(メタデータ) (2023-07-18T16:13:35Z) - Online Convex Optimization with Unbounded Memory [10.292080338245812]
OCOフレームワークの一般化である"Online Convex Optimization with Unbounded Memory"を導入する。
ポリシーの後悔に対して$O(sqrtH_p T)$上界とマッチング(Worst-case)下界を証明します。
我々は、このフレームワークの広範な適用性を、後悔境界の導出に利用し、既存の後悔境界の導出を改善し、単純化することで実証する。
論文 参考訳(メタデータ) (2022-10-18T14:43:44Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳(メタデータ) (2022-09-15T16:59:19Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳(メタデータ) (2022-01-18T17:24:20Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。
OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
論文 参考訳(メタデータ) (2021-10-24T22:43:15Z) - Early and Revocable Time Series Classification [0.028675177318965035]
本稿では,早期・無効な時系列分類という新しい問題を紹介する。
コストベースの新しいフレームワークを提案し、そこから2つの新しいアプローチを導出する。
取り消し決定の能力は、取り消し不能な体制よりもパフォーマンスを著しく向上させる。
論文 参考訳(メタデータ) (2021-09-21T16:09:11Z) - Efficient PAC Reinforcement Learning in Regular Decision Processes [99.02383154255833]
定期的な意思決定プロセスで強化学習を研究します。
我々の主な貢献は、最適に近いポリシーをパラメータのセットで時間内にPACを学習できることである。
論文 参考訳(メタデータ) (2021-05-14T12:08:46Z) - Non-stationary Online Learning with Memory and Non-stochastic Control [71.14503310914799]
我々は,過去の決定に依拠する損失関数を許容するメモリを用いたオンライン凸最適化(OCO)の問題について検討する。
本稿では,非定常環境に対してロバストなアルゴリズムを設計するための性能指標として,動的ポリシーの後悔を紹介する。
我々は,時間的地平線,非定常度,メモリ長といった面で,最適な動的ポリシーの後悔を確実に享受するメモリ付きOCOの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-07T09:45:15Z) - 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) - Bandit Linear Control [0.0]
ノイズ, 逆選択コスト, および帯域フィードバックの下で既知の線形力学系を制御することの問題点を考察する。
我々は,強い凸とスムーズなコストのために,時間的地平線の平方根で成長する後悔を得る,新しい効率的アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-01T21:12:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。