論文の概要: Online Subset Selection using $\alpha$-Core with no Augmented Regret

• arxiv url: http://arxiv.org/abs/2209.14222v1
• Date: Wed, 28 Sep 2022 16:48:58 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-29 16:38:13.062136
• Title: Online Subset Selection using $\alpha$-Core with no Augmented Regret
• Title（参考訳）: augmented Regretのない$\alpha$-Coreを用いたオンラインサブセット選択
• Authors: Sourav Sahoo, Samrat Mukhopadhyay and Abhishek Sinha
• Abstract要約: 本研究では,報奨関数の大規模クラスにおいて,SCoreと呼ばれるオンライン学習ポリシーを提案する。 サブモジュラーを含む幅広い報酬関数をSCoreポリシーを用いて効率的に学習できることが示される。
• 参考スコア（独自算出の注目度）: 7.335098632782096
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider the problem of sequential sparse subset selections in an online learning setup. Assume that the set $[N]$ consists of $N$ distinct elements. On the $t^{\text{th}}$ round, a monotone reward function $f_t: 2^{[N]} \to \mathbb{R}_+,$ which assigns a non-negative reward to each subset of $[N],$ is revealed to a learner. The learner selects (perhaps randomly) a subset $S_t \subseteq [N]$ of $k$ elements before the reward function $f_t$ for that round is revealed $(k \leq N)$. As a consequence of its choice, the learner receives a reward of $f_t(S_t)$ on the $t^{\text{th}}$ round. The learner's goal is to design an online subset selection policy to maximize its expected cumulative reward accrued over a given time horizon. In this connection, we propose an online learning policy called SCore (Subset Selection with Core) that solves the problem for a large class of reward functions. The proposed SCore policy is based on a new concept of $\alpha$-Core, which is a generalization of the notion of Core from the cooperative game theory literature. We establish a learning guarantee for the SCore policy in terms of a new performance metric called $\alpha$-augmented regret. In this new metric, the power of the offline benchmark is suitably augmented compared to the online policy. We give several illustrative examples to show that a broad class of reward functions, including submodular, can be efficiently learned using the SCore policy. We also outline how the SCore policy can be used under a semi-bandit feedback model and conclude the paper with a number of open problems.
• Abstract（参考訳）: オンライン学習環境における逐次スパースサブセット選択の問題について考察する。 集合 $[n]$ が $n$ 個の要素からなると仮定する。 $t^{\text{th}}$ ラウンドでは、モノトン報酬関数 $f_t: 2^{[N]} \to \mathbb{R}_+,$ が、$[N]の各サブセットに非負の報酬を割り当てる。 学習者は、そのラウンドに対する報酬関数$f_t$が$(k \leq n)$となる前に、$s_t \subseteq [n]$ of $k$要素を選択する。 その選択の結果、学習者は$t^{\text{th}}$のラウンドで$f_t(S_t)$の報酬を受け取る。 学習者の目標は、所定の時間軸に蓄積された累積報酬を最大化するオンラインサブセット選択ポリシーを設計することである。 そこで本研究では,大規模報酬関数の課題を解決するために,スコア(コア付きサブセット選択)と呼ばれるオンライン学習方針を提案する。 提案されたSCoreポリシーは、協調ゲーム理論の文献からCoreの概念を一般化した$\alpha$-Coreという新しい概念に基づいている。 我々は、$\alpha$-augmented regretという新しいパフォーマンス指標の観点から、SCoreポリシーの学習保証を確立します。 この新しい測定基準では、オフラインベンチマークのパワーはオンラインポリシーと比較して適切に強化されている。 スコアポリシーを用いて,サブモジュラーを含む幅広い報酬関数を効率的に学習できることを示すために,いくつかの例を示す。 また、SCoreポリシを半帯域フィードバックモデルでどのように使用できるのかを概説し、いくつかのオープンな問題で論文をまとめる。

関連論文リスト

• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  我々はMassartノイズの存在下でのオンライン学習の課題について検討する。 計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。 我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-05-21T17:31:10Z)
• Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
  3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。 次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。 この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
  論文  参考訳（メタデータ） (2023-11-23T02:19:32Z)
• Depth Dependence of $\mu$P Learning Rates in ReLU MLPs [72.14317069090407]
  我々は、最大更新(mu$P)学習率の$n$と$L$に依存することを研究する。 我々は、$L3/2.$のように、$L$の非自明な依存があることを発見した。
  論文  参考訳（メタデータ） (2023-05-13T01:10:49Z)
• Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
  対戦型オンラインマルチタスク強化学習環境について考察する。 K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。 学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
  論文  参考訳（メタデータ） (2023-01-11T02:18:26Z)
• FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
  我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。 $cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。 $mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
  論文  参考訳（メタデータ） (2021-10-19T17:43:50Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning [43.75491612671571]
  目的と目的のバランスをとる多目的強化学習について、好みを用いて検討する。 我々はこの問題をマルコフ決定過程における叙述的学習問題として定式化する。 モデルに基づくアルゴリズムは、最小限の最小限のリセットを$widetildemathcalObigl(sqrtmind,Scdot H3 SA/epsilon2bigr)$とする。
  論文  参考訳（メタデータ） (2020-11-25T21:45:04Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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