论文标题
大概知道
Probably Approximately Knowing
论文作者
论文摘要
通常保证确定性协议以获得感兴趣的特定目标，而概率协议通常仅提供概率保证。本文启动了对概率环境中代理人的作用与主观信念之间的相互依赖性的研究。特别是，我们研究了代理在执行动作时应具有的概率信念，该协议满足形式的概率约束：“条件C在执行动作A执行A时至少应具有p的可能性”。我们的主要结果是，当代理执行A时，代理商对C的预期程度等于C执行A时C所具有的概率。实际上，如果概率约束的阈值应与概率p = 1-x^2保持在某些x的小值，则概率为1-x，当代理作用时，它将分配概率的信念，而概率的信念不小于1-x，以达到C所持有的可能性。换句话说，将强烈的信念视为近似知识，代理可能必须大致知道（pak-now）C时C是真实的。
Whereas deterministic protocols are typically guaranteed to obtain particular goals of interest, probabilistic protocols typically provide only probabilistic guarantees. This paper initiates an investigation of the interdependence between actions and subjective beliefs of agents in a probabilistic setting. In particular, we study what probabilistic beliefs an agent should have when performing actions, in a protocol that satisfies a probabilistic constraint of the form: 'Condition C should hold with probability at least p when action a is performed'. Our main result is that the expected degree of an agent's belief in C when it performs a equals the probability that C holds when a is performed. Indeed, if the threshold of the probabilistic constraint should hold with probaility p=1-x^2 for some small value of x then, with probability 1-x, when the agent acts it will assign a probabilistic belief no smaller than 1-x to the possibility that C holds. In other words, viewing strong belief as, intuitively, approximate knowledge, the agent must probably approximately know (PAK-know) that C is true when it acts.
