論文の概要: Continuum-armed Bandit Optimization with Batch Pairwise Comparison Oracles
- arxiv url: http://arxiv.org/abs/2505.22361v1
- Date: Wed, 28 May 2025 13:41:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-29 17:35:50.637176
- Title: Continuum-armed Bandit Optimization with Batch Pairwise Comparison Oracles
- Title（参考訳）: バッチペアワイズ比較オラクルを用いた連続武装帯域最適化
- Authors: Xiangyu Chang, Xi Chen, Yining Wang, Zhiyi Zeng,
- Abstract要約: ここでは,関数の最大値が$f(x)$以上であるような帯域最適化問題について検討する。
このようなペアワイズ比較は、共同価格と在庫補充問題に重要な応用を見出すことを示す。
- 参考スコア（独自算出の注目度）: 14.070618685107645
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies a bandit optimization problem where the goal is to maximize a function $f(x)$ over $T$ periods for some unknown strongly concave function $f$. We consider a new pairwise comparison oracle, where the decision-maker chooses a pair of actions $(x, x')$ for a consecutive number of periods and then obtains an estimate of $f(x)-f(x')$. We show that such a pairwise comparison oracle finds important applications to joint pricing and inventory replenishment problems and network revenue management. The challenge in this bandit optimization is twofold. First, the decision-maker not only needs to determine a pair of actions $(x, x')$ but also a stopping time $n$ (i.e., the number of queries based on $(x, x')$). Second, motivated by our inventory application, the estimate of the difference $f(x)-f(x')$ is biased, which is different from existing oracles in stochastic optimization literature. To address these challenges, we first introduce a discretization technique and local polynomial approximation to relate this problem to linear bandits. Then we developed a tournament successive elimination technique to localize the discretized cell and run an interactive batched version of LinUCB algorithm on cells. We establish regret bounds that are optimal up to poly-logarithmic factors. Furthermore, we apply our proposed algorithm and analytical framework to the two operations management problems and obtain results that improve state-of-the-art results in the existing literature.
- Abstract（参考訳）: 本稿では、ある未知の強凹函数に対して、関数 $f(x)$ over T$ periods を最大化することを目標とする帯域最適化問題を考察する。
新しいペアワイズ比較オラクルを考えると、意思決定者は連続した期間に対して一対の作用を$(x, x')$とし、次に$f(x)-f(x')$と見積もる。
このようなペアワイズ比較オラクルは、共同価格と在庫補充問題やネットワーク収益管理に重要な応用を見出すことを示す。
この帯域最適化の課題は2つある。
まず、意思決定者はアクションのペア$(x, x')$を決定するだけでなく、停止時間$n$(つまり、$(x, x')$に基づくクエリの数)を決定する必要がある。
第2に、我々の在庫応用による動機付けとして、確率最適化文学における既存のオラクルとは異なる、$f(x)-f(x')$の差の見積もりがバイアスとなる。
これらの課題に対処するため、まず離散化手法と局所多項式近似を導入し、この問題を線形帯域に関連付ける。
そこで我々は、離散化されたセルをローカライズし、LinUCBアルゴリズムの対話的バッチバージョンをセル上で実行するためのトーナメント連続除去手法を開発した。
多重対数因子に最適な後悔境界を定めている。
さらに,提案したアルゴリズムと分析フレームワークを2つの運用管理問題に適用し,既存の文献の最先端結果を改善する結果を得る。
関連論文リスト
- Stopping Bayesian Optimization with Probabilistic Regret Bounds [1.4141453107129403]
我々は,ある点が与えられた条件を満たす確率に基づいて,事実上の停止規則を基準に置き換えることを検討する。
我々は,モンテカルロの停止規則を,サンプル効率が高く,推定誤差に頑健な方法で評価する実用的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-26T18:34:58Z) - Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。
提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文 参考訳（メタデータ） (2024-02-23T08:07:54Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - 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) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。