Optimization Method And Application Of Combinatorial Multi-Armed Bandit With Fairness Constraint

The rapid development of artificial intelligence and machine learning has caused social concerns about fairness.Most current machine learning algorithms focus on benefit maximization,which will lead to unfair for users.A lot of research works use multi-armed bandit model to achieve the multi-objective optimization of fairness and benefit.However,they mainly focuses on theoretical verification and has shortcomings in application.As for this,this work proposes a fair combinatorial multi-armed bandit method and applies it to distributed system,which realizes benefit maximization based on meeting fairness requirements.The main work is as follows:(1)Investigated the research background of fairness algorithms and multi-armed bandit algorithms,and sorted out related research work about fair multi-armed bandit algorithms.Most of the existing methods only consider the simulation model of small number of arms,which will cause model inaccuracy in large-scale distributed systems.For this problem,this paper designs a fair lottery algorithm F-Lottery,which makes full use of the probabilistic fairness and randomness of lottery scheduling.(2)In order to realize the multi-objective optimization of fairness and benefit,based on fair lottery algorithm and the upper confidence bound algorithm,this paper proposes a fairness combined multi-armed bandit optimization algorithm named FairLUCB.Fair lottery algorithm F-Lottery is used to quantify the fairness index,and UCB algorithm is used to achieve benefit maximization.The benefit value of fair lottery algorithm and UCB algorithm are weighted and combined to design a combined benefit value.Finally,an overall framework that takes into account both fairness and benefit has been formed.Through theoretical analysis,the logarithmic regret bound of FairLUCB algorithm is derived,and the theoretical feasibility of it is proved.(3)This paper not only uses simulation experiments to evaluate the effectiveness of the optimization method,but also applies the Fair-LUCB algorithm to client selection process in federated learning.This is a new solution framework for fairness research.In experiment,the minimum utilization rate of the client is used as the fairness requirement,and the average training accuracy maximization is used as the benefit goal.The experimental results show that the Fair-LUCB algorithm can achieve 27.4%average training accuracy higher than baseline algorithm,and achieve doubled time efficiency based on meeting fairness requirements.Experiments have proved that the proposed optimization method can achieve multi-objective optimization of fairness and training accuracy maximization in the distributed system.