論文の概要: Pareto Front Identification with Regret Minimization
- arxiv url: http://arxiv.org/abs/2306.00096v1
- Date: Wed, 31 May 2023 18:15:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 20:07:53.714923
- Title: Pareto Front Identification with Regret Minimization
- Title（参考訳）: 後悔最小化によるパレートフロント識別
- Authors: Wonyoung Kim and Garud Iyengar and Assaf Zeevi
- Abstract要約: 我々のアルゴリズムの新たな特徴は、全てのアクションのコンテキストを使用することである。
我々のアルゴリズムの新たな特徴は、全てのアクションのコンテキストを使用することである。
- 参考スコア（独自算出の注目度）: 18.208834479445894
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider Pareto front identification for linear bandits (PFILin) where the
goal is to identify a set of arms whose reward vectors are not dominated by any
of the others when the mean reward vector is a linear function of the context.
PFILin includes the best arm identification problem and multi-objective active
learning as special cases. The sample complexity of our proposed algorithm is
$\tilde{O}(d/\Delta^2)$, where $d$ is the dimension of contexts and $\Delta$ is
a measure of problem complexity. Our sample complexity is optimal up to a
logarithmic factor. A novel feature of our algorithm is that it uses the
contexts of all actions. In addition to efficiently identifying the Pareto
front, our algorithm also guarantees $\tilde{O}(\sqrt{d/t})$ bound for
instantaneous Pareto regret when the number of samples is larger than
$\Omega(d\log dL)$ for $L$ dimensional vector rewards. By using the contexts of
all arms, our proposed algorithm simultaneously provides efficient Pareto front
identification and regret minimization. Numerical experiments demonstrate that
the proposed algorithm successfully identifies the Pareto front while
minimizing the regret.
- Abstract（参考訳）: 平均報酬ベクトルが文脈の線形関数である場合、報酬ベクトルが他のいずれにも支配されないアームの集合を識別することを目的として、pareto front identification for linear bandits (pfilin) を考える。
PFILinは、特に、最高の腕識別問題と多目的能動的学習を含んでいる。
提案アルゴリズムのサンプル複雑性は$\tilde{o}(d/\delta^2)$であり、ここで$d$は文脈の次元、$\delta$は問題複雑性の尺度である。
サンプルの複雑さは対数係数まで最適です。
我々のアルゴリズムの新たな特徴は、全てのアクションのコンテキストを使用することである。
パレートフロントを効率的に同定するだけでなく、サンプルの数が$\Omega(d\log dL)$よりも大きい場合、このアルゴリズムは即時パレート後悔に対して$\tilde{O}(\sqrt{d/t})$boundを保証します。
全アームのコンテキストを利用することで,提案アルゴリズムはパレートフロントの識別と後悔の最小化を同時に行う。
数値実験により,提案アルゴリズムは後悔を最小限に抑えつつ,パレートフロントの同定に成功した。
関連論文リスト
- Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。
本手法は, 精度の高い問題に特に適している。
提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文 参考訳（メタデータ） (2023-11-08T00:10:21Z) - Bayesian Hierarchical Models for Counterfactual Estimation [12.159830463756341]
本稿では,多種多様なカウンターファクトの集合を推定する確率的パラダイムを提案する。
摂動を事前分布関数によるランダム変数として扱う。
収束特性の優れた勾配ベースサンプリング器は、後方サンプルを効率的に計算する。
論文 参考訳（メタデータ） (2023-01-21T00:21:11Z) - Transfer Learning for Contextual Multi-armed Bandits [8.97013379960904]
本研究では,コパラメトリックシフトモデルに基づく非文脈的マルチアームバンディットの移動学習問題について検討する。
ミニマックス後悔を実現する新しい伝達学習アルゴリズムを提案する。
対象領域の学習に補助的ソース領域からのデータを活用する利点を説明するため,シミュレーション研究を行った。
論文 参考訳（メタデータ） (2022-11-22T22:24:28Z) - Incentivizing Combinatorial Bandit Exploration [87.08827496301839]
自己関心のあるユーザに対してレコメンデーションシステムでアクションを推奨するバンディットアルゴリズムを考える。
ユーザーは他のアクションを自由に選択でき、アルゴリズムの推奨に従うためにインセンティブを得る必要がある。
ユーザは悪用を好むが、アルゴリズムは、前のユーザから収集した情報を活用することで、探索にインセンティブを与えることができる。
論文 参考訳（メタデータ） (2022-06-01T13:46:25Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Vector Optimization with Stochastic Bandit Feedback [10.66048003460524]
幾何学的帯域フィードバックを用いたベクトル最適化問題を導入する。
多次元平均報酬ベクトルを持つ$K$の設計を、多面的順序付けコーン$C$に従って部分的に順序付けする。
論文 参考訳（メタデータ） (2021-10-23T22:38:54Z) - Towards Deterministic Diverse Subset Sampling [14.236193187116049]
本稿では,k-DPPのグリーディ決定論的適応について論じる。
画像検索作業におけるモデルの有用性を示す。
論文 参考訳（メタデータ） (2021-05-28T16:05:58Z) - Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。
複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
論文 参考訳（メタデータ） (2020-10-21T13:43:48Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - CONSAC: Robust Multi-Model Fitting by Conditional Sample Consensus [62.86856923633923]
我々は,同じ形状の複数のパラメトリックモデルを雑音測定に適合させる頑健な推定器を提案する。
複数のモデル検出のための手作り検索戦略を利用する従来の研究とは対照的に,データから検索戦略を学習する。
探索の自己教師付き学習において,提案したアルゴリズムをマルチホログラフィー推定で評価し,最先端手法よりも優れた精度を示す。
論文 参考訳（メタデータ） (2020-01-08T17:37:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。