論文の概要: Bandit Optimal Transport
- arxiv url: http://arxiv.org/abs/2502.07397v1
- Date: Tue, 11 Feb 2025 09:24:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-12 14:10:05.790091
- Title: Bandit Optimal Transport
- Title(参考訳): 帯域最適輸送
- Authors: Lorenzo Croissant,
- Abstract要約: 本稿では,対話の繰り返しから関東性およびエントロピー性OT問題の解法を学習する際の帯域幅問題について考察する。
我々は、ヒルベルト空間上の線形包帯を拡張することにより、両方の問題に対して$tildemathcal O(sqrtT)$ regretアルゴリズムを提供する。
- 参考スコア(独自算出の注目度): 1.0878040851638
- License:
- 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) - 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) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。