在当今互联网时代，像搜索广告、众包、应用商店等互联网应用为公司创造了新的盈利渠道，也正在改变着我们的日常生活。在这些互联网应用的背后，机制（如，拍卖机制）起了至关重要的作用。近年来，最优机制设计问题已经成为博弈论和机器学习领域的研究热点课题。本文主要以搜索广告为例展开讨论。　　搜索广告系统是一个包含搜索引擎用户、广告主以及搜索引擎的多方互动的动态博弈系统。一方面，由于搜索广告系统规模大、节奏变化快，系统信息也不是完全的、透明的，因此广告主的出价行为不再是完全理性的;另一方面，由于人的本性，为了获取更多的收益，广告主的行为具有策略性，因此不再是独立同分布的，并且依赖于机制。从而在搜索广告系统中，广告主的出价行为违背了博弈论和传统机器学习中的常用假设，为最优机制设计问题带来了新的挑战。为了解决这一挑战，博弈机器学习框架被提出。这实际上是离线学习的方法，我们称其为离线博弈机器学习。它包含了两层的优化学习:首先，学习广告主的行为模型，以刻画广告主的出价变化;然后，基于学习出的广告主行为模型，模拟广告主在其他机制下的出价行为来学习最优机制。虽然实验结果表明了该方法的有效性，但是却缺乏严谨的数学描述和理论保证。此外，实际中我们往往在学习之前不能得到所有的训练样本数据，样本数据是在学习的过程中实时产生，此时需要设计在线学习的方法来优化机制。　　针对以上问题，本文做了如下三项工作:　　首先，对博弈机器学习的行为模型进行理论分析。利用随机环境中马氏链的性质，从理论上证明了在一定条件下该行为模型具有收敛性并进行了泛化能力分析。　　其次，对离线博弈机器学习进行泛化能力分析。根据离线博弈机器学习的两层经验风险最小化特点，提出度最函数空间复杂程度的新测度（即，嵌套覆盖数），并且对离线博弈机器学习的泛化误差进行分解，分解为行为学习误差和机制学习误差两部分。然后分别对行为学习误差和机制学习误差进行讨论分析，最终得到了离线博弈机器学习泛化误差上界。　　最后，对在线博弈机器学习进行探索研究。首先，设计在线博弈机器学习框架，把用该框架学习最优机制的问题转化成马氏MAB问题。其次，以最小化期望损失(Regret)为目标，设计算法，并得到该算法下的期望损失的上界。然后，设计算法考察历史数据对regret减小的程度，并给出期望损失的上界。最后，从最优机制辨认的角度设计算法，并证明用该算法得到的经验最优匹配关键词是渐近最优的。　　这三项工作，不仅从理论上对博弈机器学习的研究进行了完善，也为实际应用中的一些重要问题提供了答案，比如:如何设计数据规模，如何改进算法等。