論文の概要: 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を保証します。
全アームのコンテキストを利用することで,提案アルゴリズムはパレートフロントの識別と後悔の最小化を同時に行う。
数値実験により,提案アルゴリズムは後悔を最小限に抑えつつ,パレートフロントの同定に成功した。
関連論文リスト
- Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳(メタデータ) (2023-03-17T17:53:28Z) - Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application
to Joint Communications and Sensing [7.0997346625024]
本稿では,この問題を解決するために,変化検出を用いた汎用上信頼境界(UCB)に基づくアルゴリズムを提案する。
また,統合通信・センシングシステムにおけるエネルギー効率のよい波形設計問題を玩具の例として定式化する。
論文 参考訳(メタデータ) (2023-02-10T14:10:14Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳(メタデータ) (2022-11-28T08:40:12Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Instance-optimal PAC Algorithms for Contextual Bandits [20.176752818200438]
この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。
最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
論文 参考訳(メタデータ) (2022-07-05T23:19:43Z) - 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) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-10-13T16:35:30Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-13T05:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。