探寻优质策略及其方法

### 探寻优质策略及其方法 在策略合成与模型检查领域，如何找到优质的策略一直是研究的重点。下面将详细介绍相关的理论、算法及实验评估。 #### 1. 逻辑与策略基础 - **逻辑定义**：对于公式 \(M, q |= ⟨⟨A⟩⟩ψ U φ\) ，当且仅当存在一个统一策略 \(\sigma_A\) ，使得对于所有 \(\lambda \in outir(q, \sigma_A)\) ，存在 \(i \in N\) ，满足 \(M, \lambda[i] |= φ\) 且对于所有 \(0 \leq j < i\) ，有 \(M, \lambda[j] |= ψ\) 。同时，定义 “现在或未来某个时刻” 为 \(Fϕ \equiv⊤U ϕ\) ，即 \(M, q |= ⟨⟨A⟩⟩Fφ\) 当且仅当存在集体统一策略 \(\sigma_A\) ，在每条路径 \(\lambda \in outir(q, \sigma_A)\) 上，存在一个满足 \(φ\) 的状态。 - **模型检查与策略合成**：基于无记忆统一策略的交替时间逻辑（ATL）模型检查在显式（全局）模型大小方面是 \(\Delta P_2\) 完全的，这与解决不完全信息博弈和合成获胜策略的难度相呼应。不完全信息下的策略合成和 ATL 模型检查不仅理论上困难，实践中也颇具挑战，因为不完全信息策略难以采用基于标准短期能力算子的直接不动点算法。而完美信息策略的模型检查在计算上则便宜得多，是模型大小的 P 完全问题。 #### 2. 部分策略与策略优势 - **部分策略定义**：对于主体 \(a\) 的部分策略 \(\sigma_a\) 是一个部分函数 \(\sigma_a : St ⇀Act\) ，可扩展为完整策略。其定义域记为 \(dom(\sigma_a)\) ，对于 \(A \subseteq Agt\) ，所有部分策略的集合记为 \(\Sigma_A\) 。 - **策略结果**：对于 \(q \in dom(\sigma_A)\) ，\(\sigma_A\) 从 \(q\) 出发的结果由所有遵循该部分策略的最大路径 \(\lambda \in dom(\sigma_A)^* \cup dom(\sigma_A)^\omega\) 组成。正式定义为：\(\lambda \in out(q, \sigma_A)\) 当且仅当 \(\lambda_1 = q \land \forall i \leq |\lambda| \lambda_i \in dom(\sigma_A) \land \forall i < |\lambda| \exists \beta \in d_{Agt \backslash A}(\lambda_i) o(\lambda_i, (\sigma_A(\lambda_i), \beta)) = \lambda_{i + 1}\) 。 - **策略优势**：在给定上下文下比较两个部分策略 \(\sigma_A\) 和 \(\sigma'_A\) ，先固定上下文策略 \(\sigma_C^A\) ，若两个策略的输入状态集相等，且 \(\sigma_A\) 的输出状态集是 \(\sigma'_A\) 输出状态集的子集，则称 \(\sigma_A\) 优于 \(\sigma'_A\) 。 #### 3. 迭代策略改进的两种优势概念 - **多标准优势**：考虑基于主体 \(a\) 同一认知类的部分策略集合 \(\Sigma\) ，对于两个部分策略 \(\sigma_1\) 和 \(\sigma_2\) ，基于两个标准 \(C_1\) 和 \(C_2\) 定义优势。若 \(\sigma_2\) 在 \(C_1\) 上优于 \(\sigma_1\) 且在 \(C_2\) 上不劣于 \(\sigma_1\) ，则称 \(\sigma_2\) 以 \((C_1, C_2)\) - 优势于 \(\sigma_1\) 。进一步，若 \(\sigma_2\) 和 \(\sigma'_2\) 都以 \((C_1, C_2)\) - 优势于 \(\sigma_1\) ，且 \(\sigma'_2 \prec_{C_1} \sigma_2\) ，则称 \(\sigma_2\) 更优地以 \((C_1, C_2)\) - 优势于 \(\sigma_1\) 。若 \(\sigma_2\) 以 \((C_1, C_2)\) - 优势于 \(\sigma_1\) 且没有其他策略更优地优势于 \(\sigma_1\) ，则称 \(\sigma_2\) 最优地以 \((C_1, C_2)\) - 优势于 \(\sigma_1\) ，所有最优优势策略的集合记为 \(Best_{C_1,C_2}(\sigma_1)\) 。 - **结果与一致性优势**： - **结果标准**：给定共享输入节点集 \(In \subseteq dom(\sigma_1), dom(\sigma_2)\) ，部分策略 \(\sigma_i\) 从 \(In\) 可达的状态集记为 \(Reach(In, \sigma_i)\) ，其相关定义域 \(RDom(In, \sigma_i) = dom(\sigma_i) \cap Reach(In, \sigma_i)\) 。结果标准由关系 \(\preceq_{O(In)}\) 定义，\(\sigma_1 \preceq_{O(In)} \sigma_2\) 当且仅当 \(Reach(In, \sigma_2) \subseteq Reach(In, \sigma_1)\) ，即 \(\sigma_2\) 的可达结果状态集至少和 \(\sigma_1\) 一样紧凑。 - **一致性标准**：定义 \(\sigma_i\) 在状态集 \(Q \subseteq St\) 上的冲突集为 \(Conflicts(Q, \sigma_i) = \{(q, q') \in Q \times Q | \sigma_i(q) \neq \sigma_i(q')\}\) 。一致性标准由关系 \(\preceq_{U(In)}\) 定义，\(\sigma_1 \preceq_{U(In)} \sigma_2\) 当且仅当 \(Conflicts(RDom(In, \sigma_2), \sigma_2) \subseteq Conflicts(RDom(In, \sigma_1), \sigma_1)\) ，即 \(\sigma_2\) 在其相关定义域内遇到的所有冲突也必须出现在 \(\sigma_1\) 中。 - **优势定义**：称 \(\sigma_