ACM通信
研究突出了
技术视角:学习在不确定的环境中行动
在不确定环境下的决策问题出现在许多不同的情况下:决定是否让硬盘驱动器在网络中旋转;选择向网站访问者发布哪种广告;选择订购多少份报纸以使利润最大化;或者在交通状况信息有限甚至可能过时的情况下，选择一条路线向司机推荐。所有这些都是顺序决策问题，因为早期的决策会影响后续的性能;所有这些都需要适应性的方法，因为它们都涉及重大的不确定性。有效解决这类问题的关键问题是勘探/开发的权衡当前位置如果我正处在十字路口，在我已经探索过的道路中，什么时候应该朝着最有利的方向前进，什么时候应该朝着新的方向前进，希望能发现更好的东西?
Ganchev、Kearns、Nevmyvaka和Vaughan在下面的一篇论文中考虑了一个来自金融领域的顺序决策问题:如何在不同的市场上分配股票订单，每个市场都有未知的可用容量，从而最大限度地满足订单的数量。这些市场被称为暗池因为他们允许交易者隐藏他们的交易。这些暗池的受欢迎程度大大增加，因为进行大规模交易的交易者希望减少他们的市场影响，即价格向不利方向移动的趋势。由于交易是隐藏的，各种暗池的特征是不确定的，只有通过积极的探索才能发现。
作者所遵循的宽泛方法是基于一种直观的启发式，这让人想起你可能在书店自助区遇到的一个标题:“面对不确定性的乐观主义”。其理念是在数据允许的情况下，尽可能乐观地对待不确定的结果:选择在最好的情况下，与我们迄今为止的经验一致，并导致最佳结果的替代方案。选择一种选择可能是因为它明显优于所有其他选择，或者是因为没有足够的数据排除这种可能性。如果结果证明这个选择是一个糟糕的选择，至少它减少了不确定性，从而在未来可以自信地避免它。这种方法自然会在利用已经收集到的信息的愿望和探索不确定替代方案的需要之间取得平衡。
作者举例说明了乐观启发式如何成功地应用于暗池问题。这个结果的一个显著特征是，尽管这个问题中不同状态的数量是巨大的，但他们的方法是成功的:它在场所的数量上是指数级的。他们利用了这个问题的有利结构，特别是它在不同场地上巧妙分解的方式。他们的方法涉及对删减数据的传统非参数统计估计的修正，即在生存分析中使用的Kaplan-Meier估计。他们为每个场馆使用其中一个评估器来决定分配。他们对Kaplan-Meier估计量的修改，通过鼓励在已经充分探索过的状态空间区域边界附近进行探索，合并了乐观启发式。关键结果是，这种方法可以成功地适应未知市场:在假设不同场所的可用交易量是独立的随机变量的情况下，他们证明了他们的策略几乎可以快速执行最优配置。
本文从金融领域考虑一个顺序决策问题:如何在不同的市场上分配股票订单，每个市场都有未知的可用容量，从而使订单的数量最大化。
在面对不确定性时，乐观的启发式在其他顺序决策问题中表现良好。例如，在小的马尔可夫决策问题中，它导致学习算法的遗憾很小:每个时间步收集的效用量迅速接近最佳可能值。该领域的关键挑战是开发可以处理非常大的问题的方法:在广泛的应用中，状态空间是巨大的;暗池问题是这方面的典型问题。对于在这种情况下的良好性能，问题表现出某种有用的结构似乎是必不可少的。以下论文中详细介绍的工作展示了如何在面对不确定性时应用乐观的一般方法来开发一个非常大的顺序决策问题的结构，从而给出一个允许自动性能优化的自适应策略。这种方法肯定会得到更广泛的应用。
©2010 acm 0001-0782/10/0500 $10.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2010 ACM, Inc。
没有找到条目