論文の概要: Pure Exploration in Bandits with Linear Constraints
- arxiv url: http://arxiv.org/abs/2306.12774v4
- Date: Thu, 25 Jan 2024 11:17:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-26 18:27:45.502433
- Title: Pure Exploration in Bandits with Linear Constraints
- Title(参考訳): 線形制約をもつバンディットの純粋探査
- Authors: Emil Carlsson, Debabrota Basu, Fredrik D. Johansson, Devdatt Dubhashi
- Abstract要約: マルチアーム・バンディット・セットアップにおいて、最適ポリシーを一定の信頼度で識別する問題に対処する。
この設定に最適な2つのアルゴリズムを導入する。1つはトラック・アンド・ストップ法であり、もう1つはゲーム理論に基づく手法である。
限界を検証し、制約が問題の硬さをどのように変えるかを視覚化する実験結果を提供する。
- 参考スコア(独自算出の注目度): 15.547603114649464
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We address the problem of identifying the optimal policy with a fixed
confidence level in a multi-armed bandit setup, when \emph{the arms are subject
to linear constraints}. Unlike the standard best-arm identification problem
which is well studied, the optimal policy in this case may not be deterministic
and could mix between several arms. This changes the geometry of the problem
which we characterize via an information-theoretic lower bound. We introduce
two asymptotically optimal algorithms for this setting, one based on the
Track-and-Stop method and the other based on a game-theoretic approach. Both
these algorithms try to track an optimal allocation based on the lower bound
and computed by a weighted projection onto the boundary of a normal cone.
Finally, we provide empirical results that validate our bounds and visualize
how constraints change the hardness of the problem.
- Abstract(参考訳): 我々は,多腕バンディット設定における最適ポリシーを一定の信頼度で識別する問題に, 'emph{the arms' が線形制約を受ける際に対処する。
良く研究されている標準的な最良の腕識別問題とは異なり、この場合の最適方針は決定論的ではなく、複数の腕の間で混合することができる。
これは、情報理論の下界によって特徴づけられる問題の幾何学を変える。
本稿では,この設定に対して,トラック・アンド・ストップ法とゲーム理論に基づく2つの漸近的最適アルゴリズムを提案する。
これらのアルゴリズムは、下界に基づいて最適な割り当てを追跡し、通常の円錐の境界への重み付き投影によって計算する。
最後に,限界を検証し,制約が問題の硬さを変える様子を可視化する実験結果を提供する。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳(メタデータ) (2022-11-29T05:52:17Z) - Inverse Boundary Value and Optimal Control Problems on Graphs: A Neural
and Numerical Synthesis [0.0]
現在のアーキテクチャにおける重要な要素は、境界を注入したメッセージパッシングニューラルネットワークです。
境界から離れたノードでの予測を安定化するのに役立つグラフィカル距離に基づく正規化手法が導入された。
論文 参考訳(メタデータ) (2022-06-06T21:26:23Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - Best Arm Identification in Spectral Bandits [0.0]
BAI(Best Arm Identification)は、パラメータチューニングから臨床試験まで、多くの応用において重要な課題である。
グラフの滑らか度制約を伴う帯域モデルにおいて,信頼度を固定したベストアーム識別について検討する。
論文 参考訳(メタデータ) (2020-05-20T04:12:04Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳(メタデータ) (2017-02-16T23:42:02Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳(メタデータ) (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。