Metraipolis › archive › dc_5388732df145
AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints — arXiv:2610.07615
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.07615
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T11:41:18.019Z
- SHA-256 of the archived text
d54353d23a92658a37eb3b3f8c3bb8a3bd5658dbfeae551029c39a5281fdc870- Stable URL of this page
https://metraipolis.com/documento/dc_5388732df145
How to cite
AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints — arXiv:2610.07615 — arXiv (en), https://arxiv.org/abs/2610.07615 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5388732df145 (Metraipolis archive dc_5388732df145, sha256 d54353d23a92658a37eb3b3f8c3bb8a3bd5658dbfeae551029c39a5281fdc870)
BibTeX
@misc{dc5388732df145,
title = {AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints — arXiv:2610.07615},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.07615},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5388732df145; sha256 d54353d23a92658a37eb3b3f8c3bb8a3bd5658dbfeae551029c39a5281fdc870},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07615. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Active Feature Acquisition (AFA) is a classification problem in which an agent decides which costly features to acquire before predicting each sample's label. Unlike batch AFA, which trains a fixed policy and classifier offline on fully observed data, online AFA updates its predictor from revealed labels as samples arrive. Existing online methods either use deep reinforcement learning (RL) without performance guarantees or maximize cost-adjusted reward rather than enforce a global budget. We formulate online AFA as a combinatorial Bandits with Knapsacks (BwK) problem that couples acquisition and prediction. Unlike prior bandit-based AFA and classical BwK, our setting has combinatorial complexity, evolving rewards, a global budget, and structured side information. We obtain an improved regret upper bound over standard BwK bounds in this framework, leveraging a cardinality-aware confidence bound and the subset update structure. To avoid an exponentially large action space, we propose \emph{LP-Chain}, a variant that searches a cost-aware chain of feature subsets with a size that grows linearly with the number of features. While the regret upper bound is specific to the combinatorial framework, \emph{LP-Chain} empirically achieves comparable predictive performance. On synthetic data, \emph{LP-Chain} outperforms HEDGE-based BwK and deep RL-based online AFA baselines and scales favorably to more features.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.07615 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:24.776Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).