論文の概要: Invariant Lipschitz Bandits: A Side Observation Approach
- arxiv url: http://arxiv.org/abs/2212.07524v1
- Date: Wed, 14 Dec 2022 22:12:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-16 16:05:35.513385
- Title: Invariant Lipschitz Bandits: A Side Observation Approach
- Title（参考訳）: Invariant Lipschitz Bandits: A Side Observation Approach
- Authors: Nam Phuong Tran, The-Anh Ta, Long Tran-Thanh
- Abstract要約: 不変リプシッツ・バンディット・セッティング (invariant Lipschitz bandit set) について検討し、報酬関数と腕の集合を変換群の下で保存する。
我々は、グループ軌道を用いた側面観測を自然に統合する textttUniformMesh-N というアルゴリズムを導入する。
我々は、群が有限であることを考えると、群の濃度に依存するような改善された後悔の上界を証明する。
- 参考スコア（独自算出の注目度）: 17.43965893447343
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Symmetry arises in many optimization and decision-making problems, and has
attracted considerable attention from the optimization community: By utilizing
the existence of such symmetries, the process of searching for optimal
solutions can be improved significantly. Despite its success in (offline)
optimization, the utilization of symmetries has not been well examined within
the online optimization settings, especially in the bandit literature. As such,
in this paper we study the invariant Lipschitz bandit setting, a subclass of
the Lipschitz bandits where the reward function and the set of arms are
preserved under a group of transformations. We introduce an algorithm named
\texttt{UniformMesh-N}, which naturally integrates side observations using
group orbits into the \texttt{UniformMesh} algorithm
(\cite{Kleinberg2005_UniformMesh}), which uniformly discretizes the set of
arms. Using the side-observation approach, we prove an improved regret upper
bound, which depends on the cardinality of the group, given that the group is
finite. We also prove a matching regret's lower bound for the invariant
Lipschitz bandit class (up to logarithmic factors). We hope that our work will
ignite further investigation of symmetry in bandit theory and sequential
decision-making theory in general.
- Abstract（参考訳）: 対称性は多くの最適化と意思決定の問題に現れ、最適化コミュニティからかなりの注目を集めている。
最適化の成功にもかかわらず、特にバンディット文学において、オンライン最適化設定において対称性の利用は十分に検討されていない。
そこで本論文では、リプシッツ・バンディット・セッティング(Lipschitz bandit setting)という、リプシッツ・バンディットのサブクラスにおいて、報酬関数とアームの集合が変換群の下で保存されるような不変なリプシッツ・バンディット・セッティング(Lipschitz bandit setting)について検討する。
これは、群軌道を用いたサイドオブザーバーを、アームの集合を一様に判別する \texttt{uniformmesh-n} アルゴリズム (\cite{kleinberg2005_uniformmesh}) に統合するものである。
サイドオブザーブレーションアプローチを用いて、群が有限であることを前提に、群の濃度に依存する後悔の上界が改善されたことを証明する。
また、不変リプシッツ・バンディット類(対数因子まで)に対する後悔の下限が一致することも証明する。
我々は、バンディット理論とシーケンシャルな意思決定理論における対称性のさらなる研究に火をつけることを願っている。
関連論文リスト
- Structured Regularization for Constrained Optimization on the SPD Manifold [1.1126342180866644]
対称ゲージ関数に基づく構造化正規化器のクラスを導入し、より高速な非制約手法でSPD多様体上の制約付き最適化を解けるようにする。
構造正規化器は望ましい構造(特に凸性や凸の差)を保存または誘導するために選択できることを示す。
論文 参考訳（メタデータ） (2024-10-12T22:11:22Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback [93.57603470949266]
2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。
我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-05-27T11:23:57Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。
交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
論文 参考訳（メタデータ） (2021-09-13T16:13:13Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - The Last-Iterate Convergence Rate of Optimistic Mirror Descent in
Stochastic Variational Inequalities [29.0058976973771]
本稿では,アルゴリズムの収束率とBregman関数によって誘導される局所幾何学との複雑な関係を示す。
この指数はアルゴリズムの最適ステップサイズポリシーと得られた最適レートの両方を決定する。
論文 参考訳（メタデータ） (2021-07-05T09:54:47Z) - Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳（メタデータ） (2020-06-22T16:06:25Z) - Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。
我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
論文 参考訳（メタデータ） (2020-02-19T15:41:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。