論文の概要: Online Inverse Linear Optimization: Improved Regret Bound, Robustness to Suboptimality, and Toward Tight Regret Analysis

• arxiv url: http://arxiv.org/abs/2501.14349v4
• Date: Thu, 13 Feb 2025 07:05:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:45:10.800861
• Title: Online Inverse Linear Optimization: Improved Regret Bound, Robustness to Suboptimality, and Toward Tight Regret Analysis
• Title（参考訳）: オンライン逆線形最適化:regret境界の改善、suboptimalityへのロバスト性、およびTight Regret解析に向けて
• Authors: Shinsaku Sakaue, Taira Tsuchiya, Han Bao, Taihei Oki,
• Abstract要約: 本稿では,学習者が時間変化の可能な行動群とエージェントの最適な行動群の両方を観察するオンライン学習問題について検討する。 我々は、以前の$O(n4ln T)$の限界を$n3$の係数で改善した$O(nln T)$後悔境界を得る。
• 参考スコア（独自算出の注目度）: 25.50155563108198
• License:
• Abstract: We study an online learning problem where, over $T$ rounds, a learner observes both time-varying sets of feasible actions and an agent's optimal actions, selected by solving linear optimization over the feasible actions. The learner sequentially makes predictions of the agent's underlying linear objective function, and their quality is measured by the regret, the cumulative gap between optimal objective values and those achieved by following the learner's predictions. A seminal work by B\"armann et al. (ICML 2017) showed that online learning methods can be applied to this problem to achieve regret bounds of $O(\sqrt{T})$. Recently, Besbes et al. (COLT 2021, Oper. Res. 2023) significantly improved the result by achieving an $O(n^4\ln T)$ regret bound, where $n$ is the dimension of the ambient space of objective vectors. Their method, based on the ellipsoid method, runs in polynomial time but is inefficient for large $n$ and $T$. In this paper, we obtain an $O(n\ln T)$ regret bound, improving upon the previous bound of $O(n^4\ln T)$ by a factor of $n^3$. Our method is simple and efficient: we apply the online Newton step (ONS) to appropriate exp-concave loss functions. Moreover, for the case where the agent's actions are possibly suboptimal, we establish an $O(n\ln T+\sqrt{\Delta_Tn\ln T})$ regret bound, where $\Delta_T$ is the cumulative suboptimality of the agent's actions. This bound is achieved by using MetaGrad, which runs ONS with $\Theta(\ln T)$ different learning rates in parallel. We also provide a simple instance that implies an $\Omega(n)$ lower bound, showing that our $O(n\ln T)$ bound is tight up to an $O(\ln T)$ factor. This gives rise to a natural question: can the $O(\ln T)$ factor in the upper bound be removed? For the special case of $n=2$, we show that an $O(1)$ regret bound is possible, while we delineate challenges in extending this result to higher dimensions.
• Abstract（参考訳）: そこで,学習者は,実行可能行動の時間変化と,実行可能行動の線形最適化によって選択されたエージェントの最適行動の両方を,T$以上のラウンドで学習者が観察するオンライン学習問題について検討する。 学習者は、エージェントの根底にある線形目的関数の予測を逐次行い、その品質は、後悔、最適な目的値と学習者の予測に従うことによって達成されるものとの累積的ギャップによって測定される。 B\"armann et al (ICML 2017) によるセミナー研究は、オンライン学習手法をこの問題に適用して、$O(\sqrt{T})$の後悔の限界を達成できることを示した。 最近、Besbes et al (COLT 2021, Os. 2023) は、目標ベクトルの周囲空間の次元である$O(n^4\ln T)$ regret bound を達成することによって、結果を著しく改善した。 これらの手法は楕円体法に基づいて多項式時間で実行されるが、大きな$n$と$T$では非効率である。 本稿では、以前の$O(n^4\ln T)$の有界を$n^3$の係数で改善した$O(n\ln T)$後悔境界を得る。 我々はオンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。 さらに、エージェントのアクションが亜最適である可能性がある場合は、$O(n\ln T+\sqrt{\Delta_Tn\ln T})$ regret bound, ここで、$\Delta_T$はエージェントのアクションの累積的準最適である。 このバウンダリはMetaGradを使用して実現され、OnSを$\Theta(\ln T)$の異なる学習レートで並列に実行する。 また、$O(n\ln T)$ bound が $O(n\ln T)$ factor まで固であることを示す、$Omega(n)$ lower bound を示す単純な例も提供します。 上界の$O(\ln T)$ factorは取り除けるか? n=2$ の特別の場合、$O(1)$ 後悔境界が可能である一方で、この結果をより高次元に拡張する際の課題を明記する。

関連論文リスト

• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。 強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
  論文  参考訳（メタデータ） (2021-03-21T11:43:35Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Logistic Regression Regret: What's the Catch? [3.7311680121118345]
  パラメータに対する$L_infty$制約の下で、対数的後悔を伴う下界を導出する。 L$の制約については、十分に大きな$d$の場合、後悔は$d$で線形であるが、$T$で対数化されなくなることが示されている。
  論文  参考訳（メタデータ） (2020-02-07T18:36:39Z)

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

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