論文の概要: Learning the Pareto Front Using Bootstrapped Observation Samples
- arxiv url: http://arxiv.org/abs/2306.00096v2
- Date: Wed, 22 May 2024 20:13:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-26 21:22:37.393418
- Title: Learning the Pareto Front Using Bootstrapped Observation Samples
- Title（参考訳）: ブートストラップ観察サンプルを用いたパレートフロントの学習
- Authors: Wonyoung Kim, Garud Iyengar, Assaf Zeevi,
- Abstract要約: 本研究では,非支配的な平均報酬ベクトルを持つアームの集合を同定するアルゴリズムを提案する。
提案アルゴリズムのサンプル複雑性は対数係数まで最適である。
主要なコントリビューションは、新しい推定器で、ラウンド毎に、未知のパラメータの見積もりを複数のコンテキスト方向に沿って更新する。
- 参考スコア（独自算出の注目度）: 17.519167857253404
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider Pareto front identification (PFI) for linear bandits (PFILin), i.e., the goal is to identify a set of arms with undominated mean reward vectors 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 optimal up to a logarithmic factor. In addition, the regret incurred by our algorithm during the estimation is within a logarithmic factor of the optimal regret among all algorithms that identify the Pareto front. Our key contribution is a new estimator that in every round updates the estimate for the unknown parameter along multiple context directions -- in contrast to the conventional estimator that only updates the parameter estimate along the chosen context. This allows us to use low-regret arms to collect information about Pareto optimal arms. Our key innovation is to reuse the exploration samples multiple times; in contrast to conventional estimators that use each sample only once. Numerical experiments demonstrate that the proposed algorithm successfully identifies the Pareto front while controlling the regret.
- Abstract（参考訳）: 我々は、線形包帯(PFILin)に対するパレートフロント識別(PFI)を考える。すなわち、平均報酬ベクトルが文脈の線形関数であるときに、非支配的な平均報酬ベクトルを持つアームの集合を特定することである。
PFILinは、特に、最高の腕識別問題と多目的能動的学習を含んでいる。
提案アルゴリズムのサンプル複雑性は対数係数まで最適である。
さらに,提案アルゴリズムが推定中に生み出した後悔は,パレートフロントを識別する全てのアルゴリズムにおいて,最適後悔の対数係数の範囲内にある。
私たちの重要な貢献は、すべてのラウンドで未知のパラメータの見積もりを複数のコンテキスト方向に沿って更新する新しい推定器です。
これにより、パレートの最適な腕に関する情報を集めるために、低反射の腕を使うことができます。
我々の重要な革新は、探索サンプルを複数回再利用することであり、従来の各サンプルを1回だけ使用する推定器とは対照的である。
数値実験により,提案アルゴリズムは後悔を抑えながらパレートフロントの同定に成功した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。