Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimising the total weight, and the other one has an antagonistic objective. This combination of a qualitative reachability objective and a quantitative total-payoff objective is one of the simplest setting where Min needs memory (pseudo-polynomial in the weights) to play optimally. In this article, we aim at studying a tradeoff allowing Min to play at random, but using no memory. We show that Min can achieve the same optimal value in both cases. In particular, we compute a randomised memoryless $\varepsilon$-optimal strategy when it exists, where probabilities are parametrised by $\varepsilon$. We then characterise, and decide in polynomial time, the class of games admitting an optimal randomised memoryless strategy.


翻译:最短路径的游戏是在配有整数重量的图表上玩的双玩游戏零和游戏。 一个玩家, 我们称之为敏, 想要达到一组目标, 同时最小化总重量, 而另一个玩家则想要达到一组国家的目标, 而另一个玩家则具有对抗性的目标。 这种质量可达性目标和量化总回报目标的结合, 是Min需要记忆( 重量的假体- Polynomial ) 最优化地玩游戏的最简单环境之一 。 在此篇文章中, 我们的目标是研究一个折中法, 允许 Min 随机玩耍, 但是没有内存 。 我们显示 Min 在两种情况下都能达到相同的最佳值 。 特别是, 我们计算出一个随机化的内存 $\ varepsilon- 最佳策略, 其概率由 $\ varepsilon 匹配 。 我们然后在多音制时间决定一个游戏的类别, 接受一个最优随机化的无记忆策略 。

0
下载
关闭预览

相关内容

【经典书】算法博弈论,775页pdf,Algorithmic Game Theory
专知会员服务
148+阅读 · 2021年5月9日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
17+阅读 · 2020年9月6日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年6月22日
Arxiv
0+阅读 · 2021年6月21日
Arxiv
0+阅读 · 2021年6月21日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员