論文の概要: Confidence-Budget Matching for Sequential Budgeted Learning
- arxiv url: http://arxiv.org/abs/2102.03400v1
- Date: Fri, 5 Feb 2021 19:56:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-09 16:05:33.052394
- Title: Confidence-Budget Matching for Sequential Budgeted Learning
- Title（参考訳）: 逐次予算学習のための信頼予算マッチング
- Authors: Yonathan Efroni, Nadav Merlis, Aadirupa Saha, Shie Mannor
- Abstract要約: 問合せ予算で意思決定問題を定式化する。
我々は,多腕バンディット,線形バンディット,強化学習問題を考察する。
我々は,CBMに基づくアルゴリズムが逆性の存在下で良好に動作することを示す。
- 参考スコア（独自算出の注目度）: 69.77435313099366
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A core element in decision-making under uncertainty is the feedback on the
quality of the performed actions. However, in many applications, such feedback
is restricted. For example, in recommendation systems, repeatedly asking the
user to provide feedback on the quality of recommendations will annoy them. In
this work, we formalize decision-making problems with querying budget, where
there is a (possibly time-dependent) hard limit on the number of reward queries
allowed. Specifically, we consider multi-armed bandits, linear bandits, and
reinforcement learning problems. We start by analyzing the performance of
`greedy' algorithms that query a reward whenever they can. We show that in
fully stochastic settings, doing so performs surprisingly well, but in the
presence of any adversity, this might lead to linear regret. To overcome this
issue, we propose the Confidence-Budget Matching (CBM) principle that queries
rewards when the confidence intervals are wider than the inverse square root of
the available budget. We analyze the performance of CBM based algorithms in
different settings and show that they perform well in the presence of adversity
in the contexts, initial states, and budgets.
- Abstract（参考訳）: 不確実性の下での意思決定の核となる要素は、実行されたアクションの品質に対するフィードバックである。
しかし、多くのアプリケーションではそのようなフィードバックは制限されている。
例えば、レコメンデーションシステムでは、ユーザにレコメンデーションの品質に関するフィードバックを提供するように繰り返し求めると、イライラします。
本研究では,報酬要求数に対する(おそらく時間に依存した)ハードリミットが存在する場合,問い合わせ予算による意思決定問題を定式化する。
具体的には,多腕バンディット,線形バンディット,強化学習問題を考える。
まずは、いつでも報酬をクエリする‘greedy’アルゴリズムのパフォーマンスを分析することから始めます。
完全に確率的な環境では、驚くほどうまく機能するが、あらゆる逆境が存在する場合、これは線形な後悔につながる可能性がある。
そこで本研究では,信頼区間が利用可能な予算の逆方根よりも広い場合の報酬をクエリする信頼予算マッチング(CBM)原理を提案する。
我々は,cbmに基づくアルゴリズムの性能を異なる設定で分析し,文脈,初期状態,予算における逆境の存在下での性能を示す。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。
本手法は, 精度の高い問題に特に適している。
提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文 参考訳（メタデータ） (2023-11-08T00:10:21Z) - Best Arm Identification for Stochastic Rising Bandits [84.55453174601826]
SRB(Rising Bandits)は、選択される度に選択肢の期待される報酬が増加する、シーケンシャルな意思決定の問題をモデル化する。
本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。
R-UCBE と R-SR の2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-15T08:01:37Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Risk-aware linear bandits with convex loss [0.0]
提案手法は, 線形帯域幅の一般化に類似した, 最適リスク認識動作を学習するための楽観的 UCB アルゴリズムを提案する。
このアプローチではアルゴリズムの各ラウンドで凸問題を解く必要があり、オンライン勾配降下法によって得られる近似解のみを許すことで緩和することができる。
論文 参考訳（メタデータ） (2022-09-15T09:09:53Z) - Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits [66.02233330016435]
後悔と質問されたフィードバックの両方について、問題に依存した保証を提供します。
本稿では,問題依存的後悔と累積的フィードバック境界を導出するBuFALUというアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-12T03:24:57Z) - Algorithmic Challenges in Ensuring Fairness at the Time of Decision [6.228560624452748]
社会的文脈におけるアルゴリズムによる意思決定は、帯域幅フィードバックの下で最適化される。
最近の訴訟は、アルゴリズムによる価格設定の慣行を展開している企業を非難している。
凸最適化の文脈において、遠心自由というよく研究された公正性の概念を導入する。
論文 参考訳（メタデータ） (2021-03-16T19:06:28Z) - A One-Size-Fits-All Solution to Conservative Bandit Problems [32.907883501286]
我々は、サンプルパス報酬制約を伴う保守的なバンディット問題(CBP)のファミリーについて研究する。
CBPに対するOne-Size-Fits-Allソリューションを提案し、その応用を3つの包括問題に提示する。
論文 参考訳（メタデータ） (2020-12-14T08:50:23Z) - Reward Biased Maximum Likelihood Estimation for Reinforcement Learning [13.820705458648233]
マルコフ連鎖の適応制御のためのRBMLE(Reward-Biased Maximum Likelihood Estimate)を提案した。
我々は、現在最先端のアルゴリズムと同様に、$mathcalO( log T)$が$T$の時間的水平線上で後悔していることを示します。
論文 参考訳（メタデータ） (2020-11-16T06:09:56Z) - Constrained Upper Confidence Reinforcement Learning [12.919486518128734]
本稿では,報酬関数とコスト関数によって記述される制約が事前に不明な設定に対する高信頼強化学習を拡張した。
我々は,アルゴリズムC-UCRLが,確率1-delta$で学習しながらも,制約を満たすことなく,報酬に対するサブ線形後悔を実現することを示す。
論文 参考訳（メタデータ） (2020-01-26T00:23:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。