多玩家对数线性学习Python实现优化问题咨询

我正在针对势博弈（potential games）测试对数线性学习（log-linear learning），希望适配2名以上玩家，但遇到了代码优化瓶颈：

• 对数线性学习会诱导马尔可夫链，用转移矩阵描述状态转移，但玩家数量增加时，转移矩阵维度呈指数级增长，无法用numpy稠密数组存储
• 改用scipy稀疏矩阵后，计算（尤其是稳态分布与转移矩阵的乘法、矩阵幂运算）速度极慢

寻求多玩家场景下的可行测试方案与代码计算效率优化方法。

现有实现代码 #

1. numpy稠密矩阵实现转移矩阵 #

self.action_profiles = enumerate(np.array(list(product(np.arange(self.no_actions), repeat = self.no_players))))
        
self.potential = np.zeros((self.no_action_profiles, 1))
        
P = np.zeros([self.no_action_profiles, self.no_action_profiles])     

for idx, profile in self.action_profiles:
    
    self.potential[idx] = self.potential_function(profile)

    for player_id in range(self.no_players):
        
        mask = np.arange(len(profile)) != player_id
        opponents_actions = profile[mask] # extract the opponents actions from the action profile
        
        utilities = np.array([self.utility_functions[player_id](i, opponents_actions) for i in range(self.no_actions)])
        exp_values = np.exp(beta * utilities)

        p = exp_values/np.sum(exp_values)
        
        i = idx - profile[player_id]*self.no_actions**(self.no_players - 1 - player_id)
        stride = self.no_actions ** (self.no_players - 1 - player_id)
        
        P[idx, i: i + self.no_actions**(self.no_players - player_id) : stride] += 1/self.no_players*p
             
self.P = P

2. scipy稀疏矩阵实现转移矩阵 #

self.action_profiles = enumerate(np.array(list(product(np.arange(self.no_actions), repeat = self.no_players))))
        
self.potential = lil_matrix((self.no_action_profiles, 1))

P_row, P_col, P_data = [], [], []

for idx, profile in self.action_profiles:
    
    self.potential[idx] = self.potential_function(profile)

    for player_id in range(self.no_players):
        
        mask = np.arange(len(profile)) != player_id
        opponents_actions = profile[mask] # extract the opponents actions from the action profile
        
        utilities = np.array([self.utility_functions[player_id](i, opponents_actions) for i in range(self.no_actions)])
        exp_values = np.exp(beta * utilities)

        p = exp_values/np.sum(exp_values)
        
        i = idx - profile[player_id]*self.no_actions**(self.no_players - 1 - player_id)
        stride = self.no_actions ** (self.no_players - 1 - player_id)
        
        for j, prob in enumerate(p):
            P_row.append(idx)
            P_col.append(i + j * stride)
            P_data.append(prob / self.no_players)      

P = coo_matrix((P_data, (P_row, P_col)), shape=(self.no_action_profiles, self.no_action_profiles))
        
self.P = P.tocsr()
        
return self.P

代码使用逻辑 #

P = self.gameSetup.formulate_transition_matrix(beta)
mu0 = self.mu_matrix.copy()

self.expected_value = np.zeros((int(self.max_iter), 1))

P = np.linalg.matrix_power(P, scale_factor)

for i in range(self.max_iter):
    
    mu = mu0 @ P
    
    mu0 = mu
    
    self.expected_value[i] = mu @ self.gameSetup.potential

self.expected_value = self.expected_value
self.stationary = mu

优化方案 #

一、多玩家场景测试方案 #

1. 利用势博弈结构跳过转移矩阵

   • 对数线性学习在势博弈中的稳态分布是玻尔兹曼分布，与exp(beta * 势函数(s))成正比，无需构建转移矩阵，可直接通过势函数计算稳态分布，跳过所有矩阵运算环节
   • 若需模拟动态过程，采用蒙特卡洛采样：从初始分布出发，每次随机选一名玩家，按对数线性规则更新其动作，直接跟踪状态分布变化，无需维护完整转移矩阵

2. 近似简化测试

   • 小规模场景验证逻辑后，对大规模玩家采用均值场近似：假设所有对手动作分布一致，将多玩家问题简化为单玩家与“平均对手”的博弈，大幅压缩状态空间
   • 聚焦关键状态：只处理势函数的全局最优、局部最优等高概率状态，忽略低概率次要状态

3. 分层测试策略

   • 先测试3-4人场景验证算法正确性，再逐步扩展玩家数量；针对超大规模玩家，采用分布式采样模拟，避免单节点计算压力

二、代码计算效率优化 #

1. 转移矩阵构建优化

   • 向量化替代内层循环：在scipy版本中，用numpy向量化操作生成索引和数据，替换for j, prob in enumerate(p)循环，示例：

     # 替换内层循环
     cols = i + np.arange(self.no_actions) * stride
     rows = np.full(self.no_actions, idx)
     P_row.extend(rows)
     P_col.extend(cols)
     P_data.extend(p / self.no_players)
     

   • 预计算幂运算：提前计算self.no_actions的各次幂值，避免循环中重复计算self.no_actions**(...)
   • 批量计算效用：用numpy广播批量处理所有玩家的效用计算，替代单玩家循环

2. 稀疏矩阵运算优化

   • 避免直接矩阵幂运算：原代码中np.linalg.matrix_power(P, scale_factor)对稀疏矩阵效率极低，改用逐次乘法替代：重复执行mu0 = mu0 @ P共scale_factor次，稀疏矩阵的逐次乘法远快于直接幂运算
   • 选择最优稀疏格式：构建矩阵用coo_matrix，矩阵-向量乘法用csr_matrix，避免用lil_matrix做运算
   • 用专用稀疏库加速：采用sparse库替代scipy稀疏模块，支持更高效的稀疏数组运算

3. 稳态分布计算优化

   • 直接用势博弈稳态公式：mu(s) = exp(beta * phi(s)) / Z，其中Z是所有状态exp(beta*phi(s))的和，无需迭代计算，效率提升几个数量级
   • 若必须迭代，采用归一化幂迭代：每次乘法后对mu做归一化，避免数值溢出，同时利用稀疏矩阵的向量乘法特性

4. 数值计算优化

   • 计算exp(beta * utilities)时，先减去效用最大值避免溢出：exp_values = np.exp(beta * (utilities - np.max(utilities)))，再归一化得到概率
   • 用numba装饰potential_function和utility_functions，加速函数调用；对向量化的效用计算，用numpy广播替代循环

内容的提问来源于stack exchange，提问作者H.C.