Learning in general-sum games often yields collectively sub-optimal results. Addressing this, opponent shaping (OS) methods actively guide the learning processes of other agents, empirically leading to improved individual and group performances in many settings. Early OS methods use higher-order derivatives to shape the learning of co-players, making them unsuitable for shaping multiple learning steps. Follow-up work, Model-free Opponent Shaping (M-FOS), addresses these by reframing the OS problem as a meta-game. In contrast to early OS methods, there is little theoretical understanding of the M-FOS framework. Providing theoretical guarantees for M-FOS is hard because A) there is little literature on theoretical sample complexity bounds for meta-reinforcement learning B) M-FOS operates in continuous state and action spaces, so theoretical analysis is challenging. In this work, we present R-FOS, a tabular version of M-FOS that is more suitable for theoretical analysis. R-FOS discretises the continuous meta-game MDP into a tabular MDP. Within this discretised MDP, we adapt the $R_{max}$ algorithm, most prominently used to derive PAC-bounds for MDPs, as the meta-learner in the R-FOS algorithm. We derive a sample complexity bound that is exponential in the cardinality of the inner state and action space and the number of agents. Our bound guarantees that, with high probability, the final policy learned by an R-FOS agent is close to the optimal policy, apart from a constant factor. Finally, we investigate how R-FOS's sample complexity scales in the size of state-action space. Our theoretical results on scaling are supported empirically in the Matching Pennies environment.

对抗塑形方法 (opponent shaping) 在元博弈 (meta-game) 框架下，通过引导其他智能体的学习过程，在众多情境中提高了个体和团队的表现。作者提出 R-FOS 方法，将连续状态和动作空间的元博弈转化为表格形式，推导出一个与内部状态和动作空间的基数以及智能体数量指数相关的样本复杂度上界，保证 R-FOS 智能体所学习的最终策略与最优策略接近，除了一个常数因子外。此外，作者还探讨了 R-FOS 在状态-动作空间规模变化时的样本复杂度，并通过 Matching Pennies 环境的实证结果支持了理论上的扩展性。

对手塑形的样本复杂度分析