This paper revisits a classical problem of slotted multiple access with success, idle, and collision events on each slot. First, results of a 2-user multiple access game are reported. The game was conducted at the University of Southern California over multiple semesters and involved competitions between student-designed algorithms. An algorithm called 4-State was a consistent winner. This algorithm is analyzed and shown to have an optimal expected score when competing against an independent version of itself. The structure of 4-State motivates exploration of the open question of how to minimize the expected time to capture the channel for a $n$-user situation. It is assumed that the system delivers perfect feedback on the number of users who transmitted at the end of each slot. An efficient algorithm is developed and conjectured to have an optimal expected capture time for all positive integers $n$. Optimality is proven in the special cases $n \in \{1, 2, 3, 4, 6\}$ using a novel analytical technique that introduces virtual users with enhanced capabilities.


翻译:本文重述了每个空位的多位访问时间档、成功、闲置和碰撞的典型问题。 首先,报告了2个用户多重访问游戏的结果。 该游戏在南加州大学进行了多个学期,涉及学生设计的算法之间的竞争。 名为 4 - State 的算法始终是赢家。 该算法在与独立版本的自身竞争时被分析和显示为最佳的预期分数。 4 - State 的结构激励着探索如何最大限度地缩短为1, 2, 3, 4, 6美元获取频道的预期时间的开放问题。 假设该系统对每个空位末端传输的用户数量提供完美的反馈。 高效的算法得到开发,并预示所有正数整数的预期截取时间是最佳的 $n. 2, 3, 4, 6 6美元。 最佳性在特殊案例中得到证明 $n\ inn ein, 2, 2, 3, 4, 6, 6 使用一种引入能力增强的虚拟用户的新分析技术。

0
下载
关闭预览

相关内容

IJCAI2020接受论文列表,592篇论文pdf都在这了!
专知会员服务
63+阅读 · 2020年7月16日
【强化学习资源集合】Awesome Reinforcement Learning
专知会员服务
93+阅读 · 2019年12月23日
吴恩达新书《Machine Learning Yearning》完整中文版
专知会员服务
145+阅读 · 2019年10月27日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Accelerated Methods for Deep Reinforcement Learning
Arxiv
6+阅读 · 2019年1月10日
Arxiv
6+阅读 · 2018年4月24日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员