Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2602.09402 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914318608498688 |
|---|---|
| author | Pour, Alireza F. Mansouri, Farnam Ben-David, Shai |
| author_facet | Pour, Alireza F. Mansouri, Farnam Ben-David, Shai |
| contents | We study an online learning problem with multiple correct answers, where each instance admits a set of valid labels, and in each round the learner must output a valid label for the queried example. This setting is motivated by language generation tasks, in which a prompt may admit many acceptable completions, but not every completion is acceptable. We study this problem under three feedback models. For each model, we characterize the optimal mistake bound in the realizable setting using an appropriate combinatorial dimension. We then establish a trichotomy of regret bounds across the three models in the agnostic setting. Our results also imply sample complexity bounds for the batch setup that depend on the respective combinatorial dimensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_09402 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Learning with Multiple Correct Answers -- A Trichotomy of Regret Bounds under Different Feedback Models Pour, Alireza F. Mansouri, Farnam Ben-David, Shai Machine Learning We study an online learning problem with multiple correct answers, where each instance admits a set of valid labels, and in each round the learner must output a valid label for the queried example. This setting is motivated by language generation tasks, in which a prompt may admit many acceptable completions, but not every completion is acceptable. We study this problem under three feedback models. For each model, we characterize the optimal mistake bound in the realizable setting using an appropriate combinatorial dimension. We then establish a trichotomy of regret bounds across the three models in the agnostic setting. Our results also imply sample complexity bounds for the batch setup that depend on the respective combinatorial dimensions. |
| title | Learning with Multiple Correct Answers -- A Trichotomy of Regret Bounds under Different Feedback Models |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2602.09402 |