Robust and Learned Online Matching in Growing Trees
Abstract
We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret O(√nlog2 n), using O(n2log n) arithmetic operations and O(n) stored entries. The exact minimax rate remains open.
Related
- Robust Reconstruction on Trees with a Growing Alphabet
- Distributed online learning with growing dimensions for stochastic large regression
- Online packing of the three largest trees
- Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments
- Online Matching with Arbitrary Stochastic Rewards
BibTeX
@misc{galazka2026robust,
title = {{Robust and Learned Online Matching in Growing Trees}},
author = {Marek Gałązka and Hanna Wdowicka},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40077},
eprint = {2609.40077},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40077},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Robust and Learned Online Matching in Growing Trees
AU - Marek Gałązka
AU - Hanna Wdowicka
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40077
UR - https://arxiv.org/abs/2609.40077
AB - We study irrevocable maximum-cardinality matching in trees revealed by successive leaf attachments, with a known horizon and an exogenous growth law that is misspecified or unknown. For deterministic affine attachment forecasts with nonnegative degree reinforcement, the optimal threshold policy loses at most twice the cumulative expected conditional total-variation error relative to an online oracle knowing the actual growth law. This follows from a unit-span property of the Bellman continuation score and has no additional horizon factor. A four-vertex example attains the coefficient two for the specified deterministic policy, and a two-model argument gives a lower bound linear in the model-error budget for arbitrary policies under general misspecification. For uniform-preferential attachment, the local error has an exact expression through the leaf count. When its constant mixture parameter is unknown, we estimate it from the same growing tree and update the threshold policy at geometric times. A parameter-sensitivity bound for individual Bellman prices and uniform degree-moment estimates yield expected regret O(√nlog^2 n), using O(n^2log n) arithmetic operations and O(n) stored entries. The exact minimax rate remains open.
ER -