論文の概要: Online Learning with Ordered Experts (via Two-point Feedback)
- arxiv url: http://arxiv.org/abs/2611.07629v2
- Date: Wed, 11 Nov 2026 06:30:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:32.851667
- Title: Online Learning with Ordered Experts (via Two-point Feedback)
- Title(参考訳): 順序付きエキスパートによるオンライン学習(二点フィードバックによる)
- Abstract要約: 我々は、完全に順序付けられた行動空間において、専門家の推薦で敵対的なオンライン学習を研究する。
各ラウンドで、学習者は2つの現在のレコメンデーションを実行し、両方を観察し、平均を支払う。
動的価格設定のアプリケーションを専門家のアドバイスで提供し、2オプションメニューが最大$log$ファクターまでの完全な情報レートと一致することを示す。
- 参考スコア(独自算出の注目度): 3.7791119699394238
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study adversarial online learning with expert recommendations in a totally ordered action space, where the experts' recommendations may change and be reordered arbitrarily. Our focus is two-point feedback: on each round the learner plays two current recommendations, observes both, and pays their average. We study two problems. In the separated monotone problem, the loss is the sum of a hidden nondecreasing component and a hidden nonincreasing component, and a query reveals the two components separately. In the BV problem, the losses are bounded and have bounded variation (BV) along the order, and a query reveals only the loss. In the separated monotone problem, two paid observations achieve \[ O\bigl(\log(|\cF|T)\sqrt{T\log|\cF|}\bigr) \] regret against the best of $|\cF|$ experts, within a logarithmic factor of the classical full-information bound. For the BV problem, we obtain $\wtO(\sqrt T+|\cF|)$ regret. We give an application in dynamic pricing with expert advice, showing that two-option menus matches the full information rate up to $\log$ factors. The main technical ingredient is a marginal-preserving endpoint flow estimator. Two observations reveal a loss increment along the order; random paths supply telescoping identities that turn this local information into unbiased loss estimates for all current recommendations. A reversible pair sampler preserves the learner's intended marginal at both played actions. The estimator's second-moment and stability bounds support online updates for both feedback models.
- Abstract(参考訳): 我々は、専門家の推薦が変更され、任意に順序付けされるような、完全に秩序づけられた行動空間において、専門家の推薦で敵対的なオンライン学習を研究する。
それぞれのラウンドにおいて、学習者は2つの現在のレコメンデーションを実行し、両方を観察し、平均を支払います。
私たちは2つの問題を研究している。
分離されたモノトン問題では、損失は隠された非増分成分と隠された非増分成分の和であり、クエリは2つの成分を別々に明らかにする。
BV問題では、損失は有界であり、順序に沿って有界変動(BV)を持ち、クエリは損失のみを明らかにする。
分離された単調問題において、2つの有給観測は、古典的な全情報境界の対数係数の中で、$|\cF|$エキスパートの最高値に対して、 \[O\bigl(\log(|\cF|T)\sqrt{T\log|\cF|}\bigr) \] を後悔する。
BV問題に対して、$\wtO(\sqrt T+|\cF|)$ regretを得る。
動的価格設定のアプリケーションを専門家のアドバイスで提供し、2つのオプションメニューが最大$$$log$ファクターの完全な情報レートと一致することを示す。
主な技術要素は、限界保存エンドポイントフロー推定器である。
ランダムパスは、このローカル情報を現在のすべての推奨事項の偏りのない損失推定に変換するテレスコープIDを提供する。
可逆対サンプリング器は、双方の動作において学習者の意図した限界を保存する。
推定器の2番目のモーメントと安定性のバウンダリは、両方のフィードバックモデルに対するオンラインアップデートをサポートする。
関連論文リスト
- Online Convex Optimization with Dueling Feedback [40.61353645255313]
本研究では,オンライン凸最適化をデュエル(ペアワイズ比較)フィードバックを用いて検討し,学習者は2点間の二項選好のみを問う。
本稿では,デュエルフィードバックを近似勾配に変換するシンプルな還元法を提案する。
この還元の下では、後悔は転送を保証し、$mathcalO(T3/4)$ static, adapt, and dynamic regretを含むこの設定の最初の結果をもたらす。
論文 参考訳(メタデータ) (2026-08-15T05:26:27Z) - Capacity-Constrained Online Convex Optimization with Delayed Feedback [58.59385794080679]
容量制約下での遅延オンライン凸最適化(OCO)について検討した。
1次フィードバックの場合、容量$C = (log T)$ sufficesで標準遅延OCOレートを対数係数まで回復できることがわかった。
包帯フィードバックの場合、後悔率は$(1 + _textmax/C)$で変調される。
論文 参考訳(メタデータ) (2026-06-10T06:37:06Z) - Online Learning-to-Defer with Varying Experts [6.097236291317658]
バンディットフィードバックと動的に変化する専門家のプールを備えた,マルチクラス分類のための最初のオンラインL2Dアルゴリズムを導入する。
本手法は, 一般には$O((n+n_e)T2/3)$, $O((n+n_e)sqrtT)$を低雑音条件下で後悔保証する。
合成および実世界のデータセットの実験により、我々のアプローチは、標準的なLearning-to-Deferを、専門家の可用性と信頼性の異なる設定に効果的に拡張することを示した。
論文 参考訳(メタデータ) (2026-05-12T16:19:44Z) - Online Set Learning from Precision and Recall Feedback [60.00180898830079]
オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。
この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。
この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
論文 参考訳(メタデータ) (2026-05-10T14:28:05Z) - Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。
本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
論文 参考訳(メタデータ) (2025-10-20T02:28:08Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
論文 参考訳(メタデータ) (2024-04-16T17:59:55Z) - No-Regret Learning in Bilateral Trade via Global Budget Balance [29.514323697659613]
我々は、様々なフィードバックモデルの下で、敵対的二元貿易のための最初のノンレグレットアルゴリズムを提供する。
フルフィードバックモデルでは、学習者は後見の最高の固定価格に対して$tilde O(sqrtT)$ regretを保証できる。
また,1ビットフィードバックを伴って,$tilde O(T3/4)$ regret upper boundを保証した学習アルゴリズムも提供する。
論文 参考訳(メタデータ) (2023-10-18T22:34:32Z) - Constant regret for sequence prediction with limited advice [0.0]
予測とm$ge$2の専門家の損失を観測するために,p = 2の専門家のみを1ラウンド毎に組み合わせた戦略を提供する。
学習者が1ラウンドにつき1人の専門家のフィードバックのみを観察することを制約されている場合、最悪の場合の後悔は"スローレート"$Omega$($sqrt$KT)である。
論文 参考訳(メタデータ) (2022-10-05T13:32:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。