論文の概要: Stochastic Direct Search Method for Blind Resource Allocation
- arxiv url: http://arxiv.org/abs/2210.05222v2
- Date: Tue, 01 Oct 2024 08:15:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-02 16:31:42.379925
- Title: Stochastic Direct Search Method for Blind Resource Allocation
- Title(参考訳): ブラインド資源配置の確率的直接探索法
- Authors: Juliette Achddou, Olivier Cappe, Aurélien Garivier,
- Abstract要約: 線形制約付きおよび微分自由最適化のための直接探索法(パターン探索とも呼ばれる)について検討する。
直接探索法は決定論的かつ制約のない場合において有限の後悔を達成できることを示す。
そこで本研究では,T2/3$のオーダを後悔させるようなダイレクトサーチの簡単な拡張を提案する。
- 参考スコア(独自算出の注目度): 6.574808513848414
- License:
- Abstract: Motivated by programmatic advertising optimization, we consider the task of sequentially allocating budget across a set of resources. At every time step, a feasible allocation is chosen and only a corresponding random return is observed. The goal is to maximize the cumulative expected sum of returns. This is a realistic model for budget allocation across subdivisions of marketing campaigns, with the objective of maximizing the number of conversions. We study direct search (also known as pattern search) methods for linearly constrained and derivative-free optimization in the presence of noise, which apply in particular to sequential budget allocation. These algorithms, which do not rely on hierarchical partitioning of the resource space, are easy to implement; they respect the operational constraints of resource allocation by avoiding evaluation outside of the feasible domain; and they are also compatible with warm start by being (approximate) descent algorithms. However, they have not yet been analyzed from the perspective of cumulative regret. We show that direct search methods achieves finite regret in the deterministic and unconstrained case. In the presence of evaluation noise and linear constraints, we propose a simple extension of direct search that achieves a regret upper-bound of the order of $T^{2/3}$. We also propose an accelerated version of the algorithm, relying on repeated sequential testing, that significantly improves the practical behavior of the approach.
- Abstract(参考訳): プログラム的広告最適化によって動機づけられた予算を一連の資源に順次割り当てる作業について検討する。
ステップ毎に、実現可能なアロケーションが選択され、対応するランダムリターンのみが観察される。
目標は、期待されるリターンの累積総和を最大化することである。
これはマーケティングキャンペーンの部門をまたいだ予算配分の現実的なモデルであり、変換の数を最大化することを目的としている。
本稿では,特に逐次予算配分に適用される雑音の存在下での線形制約および微分自由度最適化のための直接探索法(パターン探索とも呼ばれる)について検討する。
これらのアルゴリズムは、リソース空間の階層的分割に依存しないため、実装が容易であり、実行可能なドメインの外での評価を回避し、リソース割り当ての運用上の制約を尊重する。
しかし、累積的後悔の観点からはまだ分析されていない。
直接探索法は決定論的かつ制約のない場合において有限の後悔を達成できることを示す。
評価ノイズと線形制約の存在下では、T^{2/3}$の残差上限を達成できるような、直接探索の単純な拡張を提案する。
また,反復的な逐次テストに頼って,アルゴリズムの高速化版を提案し,アプローチの実践的振る舞いを大幅に改善する。
関連論文リスト
- Constrained Online Two-stage Stochastic Optimization: Algorithm with
(and without) Predictions [19.537289123577022]
有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。
対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
論文 参考訳(メタデータ) (2024-01-02T07:46:33Z) - Random Exploration in Bayesian Optimization: Order-Optimal Regret and
Computational Efficiency [18.17090625880964]
本研究では,分布から引き出されたランダムサンプルを用いて領域を探索する手法について検討する。
このランダム探索手法が最適誤差率を達成することを示す。
論文 参考訳(メタデータ) (2023-10-23T20:30:44Z) - Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning [1.994307489466967]
有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。
対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
論文 参考訳(メタデータ) (2023-02-02T10:33:09Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳(メタデータ) (2022-10-04T04:43:58Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-06-22T16:07:02Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
量子化のための乗算器の交互方向法(texttADMM-Q$)アルゴリズムの性能について検討する。
不正確な更新ルールを処理できる$texttADMM-Q$のいくつかのバリエーションを開発しています。
提案手法の有効性を実証的に評価した。
論文 参考訳(メタデータ) (2020-09-08T01:58:02Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳(メタデータ) (2020-08-17T16:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。