Two-player (antagonistic) games on (possibly stochastic) graphs are a prevalent model in theoretical computer science, notably as a framework for reactive synthesis. Optimal strategies may require randomisation when dealing with inherently probabilistic goals, balancing multiple objectives, or in contexts of partial information. There is no unique way to define randomised strategies. For instance, one can use so-called mixed strategies or behavioural ones. In the most general settings, these two classes do not share the same expressiveness. A seminal result in game theory - Kuhn's theorem - asserts their equivalence in games of perfect recall. This result crucially relies on the possibility for strategies to use infinite memory, i.e., unlimited knowledge of all the past of a play. However, computer systems are finite in practice. Hence it is pertinent to restrict our attention to finite-memory strategies, defined as automata with outputs. Randomisation can be implemented in these in different ways: the initialisation, outputs or transitions can be randomised or deterministic respectively. Depending on which aspects are randomised, the expressiveness of the corresponding class of finite-memory strategies differs. In this work, we study two-player turn-based stochastic games and provide a complete taxonomy of the classes of finite-memory strategies obtained by varying which of the three aforementioned components are randomised. Our taxonomy holds both in settings of perfect and imperfect information.


翻译:双玩者( antaministic) 游戏在( 可能存在的不准确性) 图形上是理论计算机科学中流行的模型, 特别是作为反应合成的框架。 最佳战略可能需要随机化, 处理内在的概率目标时, 平衡多重目标, 或在部分信息背景下 。 没有独特的方法可以定义随机化战略 。 例如, 可以使用所谓的混合策略或行为策略。 在最普遍的设置中, 这两种类别不具有相同的表达性 。 游戏理论的任意性结果 - Kuhn's 理论 - 在完美回溯的游戏中显示其等同性 。 这个结果关键地依赖于战略使用无限记忆的可能性, 即对游戏过去所有时间的无限知识。 然而, 计算机系统在实践中是有限的 。 因此, 将我们的注意力限制在限定的模范战略上, 定义为输出的自自动化战略 。 调可以以不同的方式执行: 初始化、 产出或过渡可以随机化或确定性 。 这取决于什么方面是随机化的,, 以及我们之前三个阶段的税收战略 。

0
下载
关闭预览

相关内容

分类学是分类的实践和科学。Wikipedia类别说明了一种分类法,可以通过自动方式提取Wikipedia类别的完整分类法。截至2009年,已经证明,可以使用人工构建的分类法(例如像WordNet这样的计算词典的分类法)来改进和重组Wikipedia类别分类法。 从广义上讲,分类法还适用于除父子层次结构以外的关系方案,例如网络结构。然后分类法可能包括有多父母的单身孩子,例如,“汽车”可能与父母双方一起出现“车辆”和“钢结构”;但是对某些人而言,这仅意味着“汽车”是几种不同分类法的一部分。分类法也可能只是将事物组织成组,或者是按字母顺序排列的列表;但是在这里,术语词汇更合适。在知识管理中的当前用法中,分类法被认为比本体论窄,因为本体论应用了各种各样的关系类型。 在数学上,分层分类法是给定对象集的分类树结构。该结构的顶部是适用于所有对象的单个分类,即根节点。此根下的节点是更具体的分类,适用于总分类对象集的子集。推理的进展从一般到更具体。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
商业数据分析,39页ppt
专知会员服务
157+阅读 · 2020年6月2日
强化学习最新教程,17页pdf
专知会员服务
167+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
90+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
99+阅读 · 2019年10月9日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年4月18日
Convergence of the Discrete Minimum Energy Path
Arxiv
0+阅读 · 2022年4月15日
VIP会员
相关VIP内容
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
商业数据分析,39页ppt
专知会员服务
157+阅读 · 2020年6月2日
强化学习最新教程,17页pdf
专知会员服务
167+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
90+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
99+阅读 · 2019年10月9日
相关资讯
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员