Low-Complexity Fair Combinatorial Bandit Learning via Randomized Pick-and-Compare
This concept covers a technique for making fairness-constrained combinatorial multi-armed bandit learning computationally cheap. Instead of evaluating every feasible super arm to find the maximum-weight one (which can be exponentially many), a constant number M of feasible super arms are sampled each round and only the best among them is compared against the current selection. Holding M constant reduces per-round selection cost from exponential to constant while sacrificing fairness and regret performance only marginally.
On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit Xiaoyi Wu∗ Bo Ji† Bin
Combinatorial Multi-Armed Bandit (CMAB) with fairness constraints is an online-learning framework in which, each round, a feasible subset of arms (a 'super arm') is pulled to maximize cumulative rewa…