2024/06/30 by Gatmiry, Khashayar, Schneider, Jon · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2407.00571
We study a variant of prediction with expert advice where the learner's action at round t is only allowed to depend on losses on a specific subset of the rounds (where the structure of which rounds' losses are visible at time t is provided by a directed "feedback graph" known to the learner). We present a novel learning algorithm for this setting based on a strategy of partitioning the losses across sub-cliques of this graph. We complement this with a lower bound that is tight in many practical settings, and which we conjecture to be within a constant factor of optimal. For the important class of transitive feedback graphs, we prove that this algorithm is efficiently implementable and obtains the optimal regret bound (up to a universal constant).