論文の概要: Bandit Optimal Transport

• arxiv url: http://arxiv.org/abs/2502.07397v1
• Date: Tue, 11 Feb 2025 09:24:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 18:22:48.084093
• Title: Bandit Optimal Transport
• Title（参考訳）: 帯域最適輸送
• Authors: Lorenzo Croissant,
• Abstract要約: 本稿では,対話の繰り返しから関東性およびエントロピー性OT問題の解法を学習する際の帯域幅問題について考察する。 我々は、ヒルベルト空間上の線形包帯を拡張することにより、両方の問題に対して$tildemathcal O(sqrtT)$ regretアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 1.0878040851638
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the impressive progress in statistical Optimal Transport (OT) in recent years, there has been little interest in the study of the \emph{sequential learning} of OT. Surprisingly so, as this problem is both practically motivated and a challenging extension of existing settings such as linear bandits. This article considers (for the first time) the stochastic bandit problem of learning to solve generic Kantorovich and entropic OT problems from repeated interactions when the marginals are known but the cost is unknown. We provide $\tilde{\mathcal O}(\sqrt{T})$ regret algorithms for both problems by extending linear bandits on Hilbert spaces. These results provide a reduction to infinite-dimensional linear bandits. To deal with the dimension, we provide a method to exploit the intrinsic regularity of the cost to learn, yielding corresponding regret bounds which interpolate between $\tilde{\mathcal O}(\sqrt{T})$ and $\tilde{\mathcal O}(T)$.
• Abstract（参考訳）: 近年の統計学的最適輸送(OT)の顕著な進歩にもかかわらず、OTの「emph{sequential learning}」の研究にはほとんど関心が寄せられていない。 驚くべきことに、この問題は事実上の動機付けであり、線形バンディットのような既存の設定の挑戦的な拡張でもある。 本論では,境界が分かっているがコストが不明な場合の繰り返し相互作用から,関東ロビッチおよびエントロピーOT問題の解法を学習する確率的バンディット問題を(初めて)検討する。 我々は、ヒルベルト空間上の線形包帯を拡張することにより、両方の問題に対して$\tilde{\mathcal O}(\sqrt{T})$後悔のアルゴリズムを提供する。 これらの結果は無限次元線形包帯への還元を与える。 この次元を扱うために、学習するコストの本質的な正則性を利用する方法を提供し、$\tilde{\mathcal O}(\sqrt{T})$と$\tilde{\mathcal O}(T)$の間を補間する対応する後悔境界を得る。

関連論文リスト

• On the Optimal Regret of Locally Private Linear Contextual Bandit [18.300225068036642]
  局所的なプライベートな文脈的帯域に対して,$tilde O(sqrtT)$ regret upper bound を達成可能であることを示す。 我々の解決策は、いくつかの新しいアルゴリズム的および分析的アイデアに依存している。
  論文  参考訳（メタデータ） (2024-04-15T02:00:24Z)
• Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints [31.526232903811533]
  我々はOCO(Optimistically Safe OCO)と呼ぶアルゴリズムを導入し、そのアルゴリズムが$tildeO(sqrtT)$ regretと制約違反がないことを示す。 静的線形制約の場合、これは同じ仮定の下で、以前の最もよく知られた $tildeO(T2/3)$ regret よりも改善される。 時間的制約の場合、当社の作業は、$O(sqrtT)$ regretと$O(sqrtT)$ cumulative violationを示す既存の結果を補完します。
  論文  参考訳（メタデータ） (2024-03-09T04:01:39Z)
• Chained Information-Theoretic bounds and Tight Regret Rate for Linear Bandit Problems [37.82763068378491]
  バンドイット問題に対するトンプソン・サンプリングアルゴリズムの変形に対する後悔について検討する。 報酬の適切な連続性仮定の下で、我々の境界は、$d$次元線形バンディット問題に対して$O(dsqrtT)$の厳密なレートを提供する。
  論文  参考訳（メタデータ） (2024-03-05T23:08:18Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Learning Contextual Bandits Through Perturbed Rewards [107.6210145983805]
  標準正規性条件下では、$tildeO(tildedsqrtT)$ regret上界が達成可能であることを示す。 明示的な探索の必要性を排除するために、ニューラルネットワークを更新する際の報酬を混乱させます。
  論文  参考訳（メタデータ） (2022-01-24T19:10:22Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• Non-stationary Linear Bandits Revisited [26.082923174615495]
  非定常線形帯域は、時間変化の根底にある回帰パラメータを持つ線形帯域の変種である。 これらのアルゴリズムに対して,$widetildeO(T3/4(1+P_T)1/4)$ dynamic regretを証明した。
  論文  参考訳（メタデータ） (2021-03-09T10:07:17Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
  我々は,世界最良保証付きの最初のアルゴリズムを開発した。 損失が逆ならば、$mathcalO(log T)$ regretを達成します。 より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
  論文  参考訳（メタデータ） (2020-06-10T01:59:34Z)
• Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
  低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。 低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-04T15:30:14Z)

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

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