| Zero-sum games are a common class of game-theoretic problems that are often used to model problems in cyberspace security(e.g.,cyber attack and defense)and are of great importantance.Policy-space exploration is currently a major method to solve zero-sum games.It compresses the complete and large policy space by a relatively small population of policies to get an approximate solution,which does not rely on any model knowledge with decent quality and efficiency.However,most of the existing methods cannot fully utilize the temporal structure of the game and consider the opponent’s strategy changes in the meta-game,which results in the risk of scale explosion and performance oscillation.Meanwhile,most existing methods expand the strategy population by an online strategy learning algorithm,and repeated strategy re-solutions cause severe data underutilization.These hinder the application of policy-space exploration methods in practice.This thesis investigates these problems and aims to develop a zero-sum game solving algorithm that can be widely used to solve practical problems.Specifically,(1)a new novel extensive-form meta-game algorithm is proposed to replace the existing mainstream symmetric normal-form meta-game solving algorithm,which do not fully consider the temporal structure of the original games and the opponents’ strategy changes,and to improve the efficiency of solving meta-games.This algorithm achieves a fuller characterization of the policy space by mixing the policy members at each time step of the zero-sum games with complete consideration of the opponent’s strategies.Compared with existing methods,this method solves the problem of exploding meta-game sizes and has the advantages of stability and faster convergence;(2)A novel offline reinforcement learning algorithm is proposed to solve the problem of low data utilization in policy population expansion,which in turn significantly improves the efficiency of policy-space exploration.The method satisfy the demand for solving different target policies under the same dataset by importance weight based on the strategies of other players in the same game.Unlike single-agent offline reinforcement learning methods that solve policies in the same environment,this method does not require resampling the dataset at each iteration to learn new policies.Compared with existing methods,this method can accomplish the during expansion of the policy population in the policy-space exploration based on a static offline dataset,which has the advantage of data efficiency.Experiments are presented to demonstrate the effectiveness of the two algorithms,and each algorithm exhibits properties consistent with the theoretical derivation in respective experiments.Moreover,each algorithm shows excellent performance with excellent convergence speed and stable convergence. |
