Decentralized Online Learning with Bandit Feedback in Fair Value Games

We study decentralized online learning in task-based Fair Value Games (FVGs), where heterogeneous agents repeatedly select tasks and receive their marginal contributions to unknown, identity-dependent coalition values. We introduce OSD-FW, a projection-free Frank–Wolfe method that uses one sample per update and adapts a known template for non-convex objectives. Its new component is a sampled drift correction. The centralized form of that correction needs the joint change in every agent's policy, which no individual agent holds, and earlier decentralized methods substitute a compact summary statistic that identity-dependent values do not admit. Ours is built instead from single actions that agents draw and announce for themselves, at a per-round query cost linear in the numbers of agents and tasks. Because the Frank–Wolfe gap equals total exploitability in these games, the resulting stationarity bounds are Nash-regret bounds, with $\mathcal{O}(T^{3/4})$ under unilateral-oracle feedback, $\mathcal{O}(T^{2/3})$ once the correction is added, and $\mathcal{O}(T^{5/6})$ under pure bandit feedback, the last slower than the best rate known for this class. Under a matched value-oracle budget, the drift-corrected variant ranks fourth on average Nash gap but attains the smallest final-iterate gap among the decentralized methods tested.