論文の概要: Learning Thresholds with Latent Values and Censored Feedback
- arxiv url: http://arxiv.org/abs/2312.04653v1
- Date: Thu, 7 Dec 2023 19:30:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-11 17:33:06.209025
- Title: Learning Thresholds with Latent Values and Censored Feedback
- Title（参考訳）: 潜在値と検閲フィードバックを用いた学習閾値
- Authors: Jiahao Zhang, Tao Lin, Weiqiang Zheng, Zhe Feng, Yifeng Teng, Xiaotie
Deng
- Abstract要約: 未知の報酬$g(gamma, v)$が提案されたしきい値$gamma$と潜伏値$v$に依存する問題を示し、そのしきい値が未知の潜伏値よりも低い場合のみ$$を達成できる。
この問題は、オンラインオークションにおける予約価格の最適化、クラウドソーシングにおけるオンラインタスクの割り当て、雇用におけるリクルートバーの設定など、現実的なシナリオにおける幅広い応用がある。
- 参考スコア（独自算出の注目度）: 18.129896050051432
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we investigate a problem of actively learning threshold in
latent space, where the unknown reward $g(\gamma, v)$ depends on the proposed
threshold $\gamma$ and latent value $v$ and it can be $only$ achieved if the
threshold is lower than or equal to the unknown latent value. This problem has
broad applications in practical scenarios, e.g., reserve price optimization in
online auctions, online task assignments in crowdsourcing, setting recruiting
bars in hiring, etc. We first characterize the query complexity of learning a
threshold with the expected reward at most $\epsilon$ smaller than the optimum
and prove that the number of queries needed can be infinitely large even when
$g(\gamma, v)$ is monotone with respect to both $\gamma$ and $v$. On the
positive side, we provide a tight query complexity
$\tilde{\Theta}(1/\epsilon^3)$ when $g$ is monotone and the CDF of value
distribution is Lipschitz. Moreover, we show a tight
$\tilde{\Theta}(1/\epsilon^3)$ query complexity can be achieved as long as $g$
satisfies one-sided Lipschitzness, which provides a complete characterization
for this problem. Finally, we extend this model to an online learning setting
and demonstrate a tight $\Theta(T^{2/3})$ regret bound using continuous-arm
bandit techniques and the aforementioned query complexity results.
- Abstract（参考訳）: 本稿では、未知の報酬$g(\gamma, v)$が提案された閾値$\gamma$および潜在値$v$に依存し、その閾値が未知の潜在値よりも低い場合のみ$$$となるような潜在空間における閾値を積極的に学習する問題について検討する。
この問題は、オンラインオークションにおける予約価格の最適化、クラウドソーシングにおけるオンラインタスクの割り当て、雇用におけるリクルートバーの設定など、実用的なシナリオにおける幅広い応用がある。
まず、最適値よりも小さい$\epsilon$で閾値を学習するクエリの複雑さを特徴付け、もし$g(\gamma, v)$が$\gamma$と$v$の両方に関して単調であっても、必要なクエリ数が無限に大きくなることを証明します。
正の面では、$g$が単調で値分布のCDFがリプシッツであるとき、厳密なクエリ複雑性$\tilde{\Theta}(1/\epsilon^3)$を提供する。
さらに、厳密な$\tilde{\Theta}(1/\epsilon^3)$クエリの複雑さは、片側リプシッツ性を満たす$g$で達成でき、この問題の完全な特徴づけを提供する。
最後に、このモデルをオンライン学習環境に拡張し、前述のクエリ複雑性結果と連続アームバンディット技術を用いて、厳密な$\Theta(T^{2/3})$ regret boundを示す。
関連論文リスト
- Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。
また、最適な$(lambda, beta)$-sparsity条件に適応する適応アルゴリズムを示す。
論文 参考訳（メタデータ） (2024-10-01T13:45:55Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
対戦型オンラインマルチタスク強化学習環境について考察する。
K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。
学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
論文 参考訳（メタデータ） (2023-01-11T02:18:26Z) - A Few Expert Queries Suffices for Sample-Efficient RL with Resets and
Linear Value Approximation [16.29514743112387]
最適値関数のみを線形化可能な設定において、サンプル効率のよい強化学習(RL)について検討する。
専門的なクエリと探索をブレンドするための統計的・計算学的に効率的なアルゴリズム(Delphi)を提案する。
Delphi には $tildemathcalO(d)$ エキスパートクエリと $texttpoly(d,|mathcalA|,1/varepsilon)$ 探索サンプルの量が必要です。
論文 参考訳（メタデータ） (2022-07-18T01:39:13Z) - Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement
Learning with Latent Low-Rank Structure [9.759209713196718]
我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。
より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
論文 参考訳（メタデータ） (2022-06-07T20:39:51Z) - Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。
我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-22T03:20:40Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。