Pure Exploration with Feedback Graphs
Alessio Russo · 2025
Read Pure Exploration with Feedback Graphs by Alessio Russo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-07824.txt.
Description
Alessio Russo, Yichen Song, and Aldo Pacchiano wrote a 2025 paper on learning the best option when each try reveals only part of the picture. In their setup, a learner picks an action and sees feedback on related actions too. A graph spells out those links, covering cases from full feedback down to almost none. The goal is not to earn the most during learning, but to name the best action with confidence using few tries.
The authors derive a floor on how many samples any method needs for a given problem. The floor holds even when the graph itself is random and unknown. They show cases where the best action cannot be pinned down at all. Their results spell out how the needed samples grow with features of the graph. Last, they give a method that meets the floor in the long run, and test it across graph shapes.
Catalog record
| CREATOR | Alessio Russo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 122 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-07824