现实世界中的博弈,如兵棋推演、商业竞争、体育竞技以及日常生活中的牌类游戏等,多具有多人竞争、多次交互以及非完美信息等性质。数学上,这类问题可以被建模为竞争型扩展式非完美信息博弈（CEF-IIG:Competitive Extensive-Form Imperfect-Information Game）。鉴于这类博弈问题的广泛存在性,其求解算法具有重要的应用价值。此外,这类问题非常复杂,其求解方法与人工智能的多个领域密切相关,如树搜索、在线优化、深度学习等,因此,研究相关求解算法对促进相关领域发展也具有重要的理论意义。这类问题的复杂性主要体现在三个方面:其一,竞争型博弈的参与者之间存在对抗关系,因此无法用普通最优化方法求解;其二,扩展式博弈的性质决定了其博弈规模和求解难度与交互次数呈指数增长关系;其三,非完美信息博弈意味着博弈过程中玩家无法获得全局信息,因此用于完美信息博弈（如围棋）的相关算法不再适用。目前,求解CEF-IIG的主流方法是遗憾最小化。其中,反事实遗憾最小化算法（CFR:Counterfactual Regret Minimization）是当前实践性能最好的算法,已被成功应用于大规模德州扑克博弈。而在线凸优化算法（OCO:Online Convex Optimization）是一类经典遗憾最小化算法,其于近几年被应用于CEF-IIG,且相关理论发展迅速。遗憾最小化算法目前仍然存在数个关键问题亟待解决:1)理论与实践不一致问题。一方面,CFR算法的实际收敛速度显著快于理论速度;另一方面,OCO算法的理论优势未能转化为实践优势。2)收敛慢问题。传统遗憾最小化算法需要迭代非常多次才能获得一个可接受的近似解,在实践应用中难以令人满意。3)在大规模博弈中效率低问题。传统方法计算消耗大,存储需求高,且依赖基于模型的采样方法,导致无法应用于更多难以建模的大规模博弈问题。针对这些问题,本文研究面向竞争型扩展式非完美信息博弈的遗憾最小化算法。具体地,针对理论与实践不一致问题,本文研究建立CFR算法与OCO算法之间的等价关系,以为改进CFR算法的理论结果和OCO算法的实践性能开辟新的研究路径;针对收敛慢问题,本文研究自适应乐观OCO算法,以同时提高OCO算法的理论和实践收敛速度;针对在大规模博弈中效率低问题,本文研究高效的基于无模型采样和神经网络的CFR算法。本文的主要工作和创新点总结如下:针对理论与实践不一致问题,本文建立并证明了 CFR算法与OCO算法的等价关系,为CFR算法的性能优势提供了新的理论解释,同时,提高了 OCO算法的实践性能。具体地,本文设计了一种新型的OCO算法,并证明了它与CFR算法等价。该等价关系可以将CFR算法解释为一种自适应OCO算法,从而在理论上间接解释了其性能优势。其次,本文借鉴CFR算法的自适应性,提出了一种基于“未来策略”的OCO算法,并在多种CEF-IIG上深入研究了其收敛性质。结果表明,新型基于未来策略的OCO算法不仅显著快于传统OCO算法,在某些CEF-IIG上甚至快于当前最先进的CFR算法。针对收敛慢问题,本文推广现有乐观OCO算法,提出了一种具有显著理论优势的自适应改进算法,在此基础上,结合前一工作,提出了一种高效的基于未来策略的自适应算法。具体地,本文推广了现有乐观OCO算法,使其具有自适应能力,并且通过改进其正则化函数,显著改善了其可利用度上界（对博弈深度的依赖从指数级降低到多项式级）。其次,本文基于OCO与CFR算法的等价关系,提出了一种高效的基于未来策略的自适应乐观OCO算法,并且证明它在一定条件下等价于一种基于预测的CFR算法,从而为后者提供了新的理论解释。实验结果表明,本文提出的自适应乐观OCO算法显著好于同类算法,并且基于未来策略的自适应乐观OCO算法在多种CEF-IIG上快于基于预测的CFR算法。针对在大规模博弈中效率低问题,本文提出了一种基于无模型采样和神经网络的CFR算法,在避免有模型采样所带来的问题的同时,显著提高了训练效率。具体地,本文提出了一种具有递归性质的新型CFR算法并证明了其收敛性。该算法的特点是不需要跟踪每个决策点的累积反事实遗憾。基于新型CFR算法,本文提出了一种基于无模型采样和神经网络的CFR算法。该算法不需要近似累积反事实遗憾,而只需要近似一种非累积的递归替代价值,因而其训练效率显著高于其他同类算法。在大规模博弈的实验结果表明,新算法不仅训练效率更高,其性能也达到甚至超过了当前最优算法的水平。