摘要

本文介绍了一种基于上下文组合多臂老虎机（Contextual Combinatorial Multi-Armed Bandits）的谈判策略学习方法，旨在解决谈判中的两大关键挑战：探索-利用困境（exploration-exploitation dilemma）和大动作空间问题。该方法通过组合多臂老虎机解决了探索-利用困境，并通过其组合性质处理大动作空间。此外，本文还引入了NegUCB算法，该算法能够处理谈判中的部分观测和复杂奖励函数问题。NegUCB算法在温和假设下保证了次线性的后悔上界，并通过在三个谈判任务上的实验证明了其优越性。

原理

NegUCB算法的核心在于利用上下文组合多臂老虎机框架来处理谈判问题。在这个框架中，每个“臂”代表谈判中的一个项目，而“超级臂”则代表一个由多个项目组成的出价。奖励函数被定义为对手接受出价的概率，值为1表示接受，0表示拒绝。NegUCB算法通过迭代学习过程，不断优化出价策略，同时处理探索-利用困境和部分观测问题。算法通过内核回归（kernel regression）来处理复杂的接受函数，确保在谈判步骤数量增加时，累积后悔（cumulative regret）以次线性速度增长，且与出价数量无关。

流程

NegUCB算法的工作流程包括以下步骤：

1. 初始化：设定参数和内核函数。
2. 选择出价：根据当前的学习策略和探索参数，选择一个出价。
3. 观测反馈：观测对手是否接受出价，并记录结果。
4. 更新模型：利用观测到的反馈更新接受函数的估计。
5. 重复步骤2-4，直到谈判结束。 具体来说，算法在每个时间步骤选择一个出价，并根据对手的反馈更新模型参数。通过这种方式，算法能够在探索新出价和利用已知信息之间找到平衡，从而优化长期的谈判结果。

应用

NegUCB算法适用于多种谈判场景，包括贸易、资源分配和多议题谈判等。由于其能够处理大动作空间和部分观测问题，该算法在复杂的现实世界谈判任务中具有广泛的应用前景。特别是在需要与多个对手进行谈判的场景中，NegUCB算法能够提供有效的策略学习支持，帮助谈判者达成更有利的协议。