論文の概要: Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets

• arxiv url: http://arxiv.org/abs/2602.01682v1
• Date: Mon, 02 Feb 2026 05:48:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:33.936543
• Title: Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
• Title（参考訳）: オンライン逆線形最適化におけるM-凸作用集合の有限・破壊・破壊再帰境界
• Authors: Taihei Oki, Shinsaku Sakaue,
• Abstract要約: 本研究では,コンテキストレコメンデーションとして知られる逆逆線形最適化について検討する。 学習者は、M-集合上の最適解のキャラクタリゼーションとボリューム引数を組み合わせることで、これを後悔する。
• 参考スコア（独自算出の注目度）: 27.973926244529267
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online inverse linear optimization, also known as contextual recommendation, where a learner sequentially infers an agent's hidden objective vector from observed optimal actions over feasible sets that change over time. The learner aims to recommend actions that perform well under the agent's true objective, and the performance is measured by the regret, defined as the cumulative gap between the agent's optimal values and those achieved by the learner's recommended actions. Prior work has established a regret bound of $O(d\log T)$, as well as a finite but exponentially large bound of $\exp(O(d\log d))$, where $d$ is the dimension of the optimization problem and $T$ is the time horizon, while a regret lower bound of $Ω(d)$ is known (Gollapudi et al. 2021; Sakaue et al. 2025). Whether a finite regret bound polynomial in $d$ is achievable or not has remained an open question. We partially resolve this by showing that when the feasible sets are M-convex -- a broad class that includes matroids -- a finite regret bound of $O(d\log d)$ is possible. We achieve this by combining a structural characterization of optimal solutions on M-convex sets with a geometric volume argument. Moreover, we extend our approach to adversarially corrupted feedback in up to $C$ rounds. We obtain a regret bound of $O((C+1)d\log d)$ without prior knowledge of $C$, by monitoring directed graphs induced by the observed feedback to detect corruptions adaptively.
• Abstract（参考訳）: そこで,学習者がエージェントの隠れた対象ベクトルを,時間とともに変化する実行可能な集合に対して観測された最適行動から逐次推測する。 学習者は、エージェントの真の目的の下でうまく機能するアクションを推奨することを目的としており、そのパフォーマンスは、エージェントの最適な値と学習者の推奨アクションによって達成されるものとの累積的なギャップとして定義される後悔によって測定される。 以前の研究は、$O(d\log T)$の後悔境界と、有限だが指数関数的に大きい$\exp(O(d\log d))$の後悔境界を確立しており、$d$は最適化問題の次元であり、$T$は時間地平線であり、後悔の低い$Ω(d)$は知られている(Gollapudi et al 2021; Sakaue et al 2025)。 d$ の有限後悔束縛多項式が達成可能であるか否かは、未解決の問題のままである。 実現可能な集合が、マトロイドを含む広いクラスであるM-凸であるとき、有限後悔境界の$O(d\log d)$が可能であることを示すことで、これを部分的に解決する。 このことは、M-凸集合上の最適解の構造的特徴と幾何体積の引数を組み合わせることによって達成される。 さらに、我々のアプローチを拡張して、反対に破損したフィードバックを最大$C$ラウンドに拡張する。 我々は、観測されたフィードバックによって誘導される有向グラフを監視して、$O((C+1)d\log d)$の遺言境界を$C$の事前知識なしで取得し、汚職を適応的に検出する。

関連論文リスト

• Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound [25.50155563108198]
  ラウンド単位の複雑さが$T$に依存しない最初の対数-回帰法を提案する。 我々の方法は極めて単純であり、オンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。 また、$Omega(n)$ の下限を示し、$O(nln T)$ 境界が $O(ln T)$ 係数まで固であることを示す。
  論文  参考訳（メタデータ） (2025-01-24T09:19:15Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。