RECORD
Online Subset Selection using $\alpha$-Core with no Augmented Regret
Machine Learning · Submitted 28 Sep 2022
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that a large class of reward functions, including submodular, can be efficiently optimized with the SCore policy.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We revisit the classic problem of optimal subset selection in the online learning set-up. Assume that the set $[N]$ consists of $N$ distinct elements. On the $t$th round, an adversary chooses a monotone reward function $f_t: 2^{[N]} \to \mathbb{R}_+$ that assigns a non-negative reward to each subset of $[N].$ An online policy selects (perhaps randomly) a subset $S_t \subseteq [N]$ consisting of $k$ elements before the reward function $f_t$ for the $t$th round is revealed to the learner. As a consequence of its choice, the policy receives a reward of $f_t(S_t)$ on the $t$th round. Our goal is to design an online sequential subset selection policy to maximize the expected cumulative reward accumulated over a 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 polyhedral characterization of the reward functions called $\alpha$-Core - a generalization 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 performance of the online policy is compared with an unrestricted offline benchmark that can select all $N$ elements at every round. We show that a large class of reward functions, including submodular, can be efficiently optimized with the SCore policy. We also extend the proposed policy to the optimistic learning set-up where the learner has access to additional untrusted hints regarding the reward functions. Finally, we conclude the paper with a list of open problems.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We revisit the classic problem of optimal subset selection in the online learning set-up. | background 0.99 | 0.39 | 0.03 | unclear 0.55 |
| s1 | Assume that the set $[N]$ consists of $N$ distinct elements. | background 1.00 | 0.06 | 0.01 | asserted 0.98 |
| s2 | On the $t$th round, an adversary chooses a monotone reward function $f_t: 2^{[N]} \to \mathbb{R}_+$ that assigns a non-negative reward to each subset of $[N].$ An online policy selects (perhaps randomly) a subset $S_t \subseteq [N]$ consisting of $k$ elements before the reward function $f_t$ for the $t$th round is revealed to the learner. | background 0.99 | 0.07 | 0.02 | asserted 0.91 |
| s3 | As a consequence of its choice, the policy receives a reward of $f_t(S_t)$ on the $t$th round. | background 0.98 | 0.12 | 0.02 | asserted 1.00 |
| s4 | Our goal is to design an online sequential subset selection policy to maximize the expected cumulative reward accumulated over a time horizon. | background 0.96 | 0.15 | 0.05 | asserted 0.94 |
| s5 | 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. | contribution 0.85 | 0.93 | 0.22 | asserted 1.00 |
| s6 | The proposed SCore policy is based on a new polyhedral characterization of the reward functions called $\alpha$-Core - a generalization of Core from the cooperative game theory literature. | method 0.72 | 0.84 | 0.09 | asserted 1.00 |
| s7 | We establish a learning guarantee for the SCore policy in terms of a new performance metric called $\alpha$-augmented regret. | contribution 0.56 | 0.95 | 0.23 | asserted 1.00 |
| s8 | In this new metric, the performance of the online policy is compared with an unrestricted offline benchmark that can select all $N$ elements at every round. | method 0.56 | 0.50 | 0.06 | asserted 0.95 |
| s9 | We show that a large class of reward functions, including submodular, can be efficiently optimized with the SCore policy. | result 0.92 | 0.94 | 0.32 | asserted 1.00 |
| s10 | We also extend the proposed policy to the optimistic learning set-up where the learner has access to additional untrusted hints regarding the reward functions. | contribution 0.99 | 0.91 | 0.05 | asserted 1.00 |
| s11 | Finally, we conclude the paper with a list of open problems. | future work 1.00 | 0.55 | 0.04 | unclear 0.65 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We revisit the classic problem of optimal subset selection in the online learning set-up. Assume that the set $[N]$ consists of $N$ distinct elements. On the $t$th round, an adversary chooses a monotone reward function $f_t: 2^{[N]} \to \mathbb{R}_+$ that assigns a non-negative reward to each subset of $[N].$ An online policy selects (perhaps randomly) a subset $S_t \subseteq [N]$ consisting of $k$ elements before the reward function $f_t$ for the $t$th round is revealed to the learner. As a consequence of its choice, the policy receives a reward of $f_t(S_t)$ on the $t$th round. Our goal is to design an online sequential subset selection policy to maximize the expected cumulative reward accumulated over a 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 polyhedral characterization of the reward functions called $\alpha$-Core - a generalization 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 performance of the online policy is compared with an unrestricted offline benchmark that can select all $N$ elements at every round. We show that a large class of reward functions, including submodular, can be efficiently optimized with the SCore policy. We also extend the proposed policy to the optimistic learning set-up where the learner has access to additional untrusted hints regarding the reward functions. Finally, we conclude the paper with a list of open problems.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 5 sentences without a confident label
Builds on 1 paper
-
This bound can be generalized for $γ$-weakly submodular functions [ref] as well, where one can similarly derive a $γ(1-c)$-approximate static regret guarantee with the policy.
Weakly Submodular Function Maximization Using Local Submodularity Ratio · Comparison between the Augmented and Standard Regret for Submodular functions · 0.93
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.