論文の概要: Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

• arxiv url: http://arxiv.org/abs/2609.26978v1
• Date: Tue, 22 Sep 2026 19:13:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 00:05:17.737947
• Title: Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
• Title（参考訳）: マルチスケール行列重みを用いたオンライン逆線形最適化のためのタイトレグレト境界
• Abstract要約: 固定された未知の線形効用を用いた逆線形最適化について検討する。 各ラウンドにおいて、環境はコンパクトなアクションセットを示し、学習者はそれからアクションを推奨し、環境は同じセット上でユーティリティを最大化するアクションを返す。 効用ベクトルと作用が$d$次元ユークリッド単位球に置かれるとき、我々は無作為なアルゴリズムを与える-------------------------------------------------- (sqrt d)$------------------------------------------------------------------------------------------------- -------------------
• 参考スコア（独自算出の注目度）: 18.046669772867443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the $d$-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is $O(\sqrt d)$ in expectation for every time horizon, without knowledge of the horizon. The dependence on $d$ is optimal up to a constant factor by the known $Ω(\sqrt d)$ lower bound for horizons $T\ge d$. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the $O(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.
• Abstract（参考訳）: 固定された未知の線形ユーティリティを用いてオンライン逆線形最適化について検討し、各ラウンドにおいて、環境がコンパクトなアクションセットを示し、学習者はそれからアクションを推奨し、環境は同じ集合上でユーティリティを最大化するアクションを返す。 効用ベクトルと作用が$d$次元ユークリッド単位球に置かれるとき、最適作用に対する累積効用短絡------ は地平線を知らずに全ての時間地平線を予想して$O(\sqrt d)$ となるような無作為化アルゴリズムを与える。 d$への依存は、既知の$Ω(\sqrt d)$ lower bound for horizons $T\ge d$によって定数因子に最適化される。 我々のアルゴリズムは、幾何学的空間スケールでの多項式特徴空間上の行列乗法重みを維持できる。 線形プログラムを解くことでレコメンデーション分布を選択し、利用可能なアクションとフィードバックアクションを比較してスコア行列を更新する。 有理オラクル出力とフィードバックアクションにより、線形最適化オラクルに対して計算可能な実装は、$O(\sqrt d)$ regret boundを保存する。 同じ速度が次元、地平線、入力長のランニング時間多項式で達成できるかどうかは未定である。

関連論文リスト

• Learning to Sparsify Stochastic Linear Bandits [12.61900668356141]
  本稿では,高次元空間から連続的に行動を選択する線形帯域幅の分散化を学習する問題に対処する。 本稿では,パラメータ学習のための最小二乗法と,スパース動作選択のための特別サブルーチンを用いて,適応的に段階的に探索・利用を行うアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2026-05-11T07:57:37Z)
• End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions [66.17960480460185]
  決定過程(MDP)における線形関数近似を用いた強化学習の研究 本稿では, 線形ベルマン完全オラクルに対して, 決定論的遷移, 初期状態, 報奨を伴う計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-24T17:32:29Z)
• Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets [27.973926244529267]
  本研究では,コンテキストレコメンデーションとして知られる逆逆線形最適化について検討する。 学習者は、M-集合上の最適解のキャラクタリゼーションとボリューム引数を組み合わせることで、これを後悔する。
  論文  参考訳（メタデータ） (2026-02-02T05:48:54Z)
• 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)
• Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation [1.8416014644193066]
  ベルマン最適条件下で線形マルコフ決定過程(MDP)と線形混合MDPを学習するアルゴリズムを提案する。 線形MDPに対する我々のアルゴリズムは、$widetildemathcalO(d3/2mathrmsp(v*)sqrtT)$ over $T$タイムステップの最もよく知られた後悔の上限を達成する。 線形混合 MDP に対して、我々のアルゴリズムは、$widetildemathcalO(dcdotmathrm) の後悔境界に達する。
  論文  参考訳（メタデータ） (2024-09-16T23:13:42Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)

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

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