2.3.2 随机博弈公式

由于本章考虑的系统中有多个设备，因此它们可以在计算过载时将任务卸载到其他设备，或者在负载不足时帮助其他设备计算卸载的任务。为了在 N 个设备之间达到纳什均衡，可以将它们之间的相互作用建模为随机博弈过程，并用一个元组来表示，详细介绍如下。

① S 表示分布式系统的状态空间，其中包含与设备和任务有关的所有可能状态。st表示系统在时隙t时的状态，其中。为时隙t时的瞬时网络连通图；分别表示每个设备的传输队列和处理队列的状态；表示设备的处理能力，表示任务生成强度。

② O 表示系统中的设备观测空间。由于在本章的分布式系统中没有进行集中控制，因此对设备的观察与系统状态是不同的。表示设备i在时隙t的观测，并且。在这里，可以包含前一个时隙记录的部分系统状态，而当前时隙中记录其他的系统状态。

③ A表示任务的行动空间，包括设备的选择动作和任务的决策动作，从设备的角度来看，向量at是时隙t中所有设备的动作集合，表示为。动作表示设备在时隙t中可以执行的操作，即是否卸载本地任务，以及应该选择哪个设备来处理卸载的任务。从任务的角度来看，表示任务xi,k的动作，在设备i上可能有多个任务需要在时隙t被调度，即。当任务在本地处理时，动作；否则。因此，动作空间可以表示为A={1,2,…,j,…,N}。此外，本章还假设每个设备在不知道其他设备的动作时独立决定自己的动作。

④ 表示状态转移概率矩阵，其中p(st+1|st,at)表示状态st根据动作at转移到状态st+1的概率。

⑤ R表示奖励，其中表示设备i在时隙t中根据系统状态st和动作所获得的奖励。一个任务的奖励可以通过来计算。

⑥ 符号ρ0是系统初始状态st的分布。

⑦ γ∈(0,1)是期望奖励的折扣因子。

基于上述公式化的随机博弈，可以建立平均任务完成时间与累积奖励之间的关系。

定理2.1 累积奖励：每个设备的平均任务完成时延可以被重新描述为，其中操作符“”表示接近。

根据定理2.1，本章所提算法的目的是使期望的累积折扣奖励最大化，如式（2-6）所示。

系统中每个设备都试图最大化其累积的折扣奖励。对于多个设备，应该设计一个可以分布式执行的神经网络，并保证它们之间的纳什均衡。πi和π−i分别表示设备i和其他设备采取的策略。同时，策略和代表相应的最优策略。系统中达到纳什均衡的定义如下所示。

定义2.1 纳什均衡：当设备训练马尔可夫策略以满足条件，其中i∈并且st∈S，已建立的随机博弈已经被证明可以达到纳什均衡，其中是设备 i 的状态值，可以通过 计算得到。之后，将变量互换。