論文の概要: Rank-Regret Minimization

• arxiv url: http://arxiv.org/abs/2111.08563v1
• Date: Tue, 16 Nov 2021 15:39:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-17 16:19:25.900521
• Title: Rank-Regret Minimization
• Title（参考訳）: ランクレグレット最小化
• Authors: Xingxing Xiao and Jianzhong Li
• Abstract要約: 近年, 後悔最小化セット (RMS) クエリが提案されている。 RMS はデータセット D の固定サイズ部分集合 S を返します。 既存の研究によると、後悔率はユーザーの後悔レベルを正確に定量化できない。
• 参考スコア（独自算出の注目度）: 9.890133441628413
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-criteria decision-making often requires finding a small representative subset from the database. A recently proposed method is the regret minimization set (RMS) query. RMS returns a fixed size subset S of dataset D that minimizes the regret ratio of S (the difference between the score of top1 in S and the score of top-1 in D, for any possible utility function). Existing work showed that the regret-ratio is not able to accurately quantify the regret level of a user. Further, relative to the regret-ratio, users do understand the notion of rank. Consequently, it considered the problem of finding a minimal set S with at most k rank-regret (the minimal rank of tuples of S in the sorted list of D). Corresponding to RMS, we focus on the dual version of the above problem, defined as the rank-regret minimization (RRM) problem, which seeks to find a fixed size set S that minimizes the maximum rank-regret for all possible utility functions. Further, we generalize RRM and propose the restricted rank-regret minimization (RRRM) problem to minimize the rank-regret of S for functions in a restricted space. The solution for RRRM usually has a lower regret level and can better serve the specific preferences of some users. In 2D space, we design a dynamic programming algorithm 2DRRM to find the optimal solution for RRM. In HD space, we propose an algorithm HDRRM for RRM that bounds the output size and introduces a double approximation guarantee for rank-regret. Both 2DRRM and HDRRM can be generalized to the RRRM problem. Extensive experiments are performed on the synthetic and real datasets to verify the efficiency and effectiveness of our algorithms.
• Abstract（参考訳）: 複数基準の意思決定では、データベースから小さな代表サブセットを見つける必要があることが多い。 最近提案された手法は、remove minimization set (rms) クエリである。 rms はデータセット d の固定サイズのサブセット s を返し、s の後悔率を最小にする(s の top1 のスコアと d の top-1 のスコアの違いは、任意のユーティリティ関数に対して)。 既存の研究によると、後悔率はユーザーの後悔レベルを正確に定量化できない。 さらに、後悔率に対して、ユーザはランクの概念を理解している。 その結果、最小集合 S を少なくとも k 階数レグレット(D のソートされたリストにおける S のタプルの最小ランク)で見つけるという問題を検討した。 RMSに対応して、上述の問題をランクレグレット最小化(RRM)問題として定義し、可能なすべてのユーティリティ関数の最大ランクレグレットを最小化する固定サイズセットSを求める。 さらに、 RRM を一般化し、制限空間における関数に対する S の階数の最小化(RRRM)問題を提案する。 RRRMのソリューションは、通常、低い後悔レベルを持ち、一部のユーザの特定の好みに役立てることができる。 2次元空間において、RRMの最適解を見つけるために動的プログラミングアルゴリズム2DRRMを設計する。 hd空間において、出力サイズを制限したrrmのためのアルゴリズムhdrrmを提案し、ランクレグレットに対する二重近似保証を導入する。 2DRRMもHDRRMもRRRM問題に一般化できる。 アルゴリズムの効率と有効性を検証するために,合成データと実データを用いて広範な実験を行った。

関連論文リスト

• Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Bandits [3.5502600490147196]
  我々は、シャープ比(SR)が金融時系列の特徴付けにおける重要なパラメータであると考えている。 我々は、レギュレット最小化(RM)とBest Arm Identification(BAI)のために、UCB-RSSRと呼ばれるSRを最適化する新しいアルゴリズムを提案する。 UCB-RSSRは、他のSR最適化バンディットアルゴリズムであるU-UCB Cassel et al(2023)よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-05-28T14:24:36Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
  リスクに敏感な強化学習(RL)について検討する。 本稿では, CVaR RLにおける探索, 搾取, 表現学習の相互作用のバランスをとるための, 新たなアッパー信頼境界(UCB)ボーナス駆動アルゴリズムを提案する。 提案アルゴリズムは,各エピソードの長さが$H$,アクション空間が$A$,表現の次元が$d$であるような,エプシロン$最適CVaRのサンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2023-11-20T17:44:40Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Super-Resolution Information Enhancement For Crowd Counting [29.285992361194467]
  既存の手法は、低分解能(LR)環境を無視しながら、観客数を効果的に処理する。 マルチスケール超解法モジュール(MSSRM)と呼ばれるよりエレガントな手法を提案する。 提案手法はSRラベルを必要とするため,さらに超解答クラウドカウントデータセット(SR-Crowd)を提案する。
  論文  参考訳（メタデータ） (2023-03-13T08:41:24Z)
• Best Arm Identification for Stochastic Rising Bandits [84.55453174601826]
  SRB(Rising Bandits)は、選択される度に選択肢の期待される報酬が増加する、シーケンシャルな意思決定の問題をモデル化する。 本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。 R-UCBE と R-SR の2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-15T08:01:37Z)
• New Tight Relaxations of Rank Minimization for Multi-Task Learning [161.23314844751556]
  2つの正規化項に基づく2つの新しいマルチタスク学習定式化を提案する。 本手法は,タスク間で共有される低ランク構造を正確に復元し,関連するマルチタスク学習方法より優れていることを示す。
  論文  参考訳（メタデータ） (2021-12-09T07:29:57Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Constrained regret minimization for multi-criterion multi-armed bandits [5.349852254138086]
  リスク制約を条件として,所与の時間的地平線上での後悔の最小化の問題について検討する。 本稿では,対数的後悔を保証するリスク制約付き低信頼境界アルゴリズムを提案する。 我々は,リスク制約付き後悔最小化アルゴリズムの性能に低い限界を証明した。
  論文  参考訳（メタデータ） (2020-06-17T04:23:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。