Incorporation of Optimal Computing Budget Allocation for Ordinal Optimization Into Learning Automata
Incorporation of Optimal Computing Budget Allocation for Ordinal Optimization Into Learning Automata
复制标题
DOI：
10.1109/tase.2015.2450535
复制
发表时间：
2016-04
影响因子：
5.6
通讯作者：
Junqi Zhang;Cheng Wang;D. Zang;Mengchu Zhou
中科院分区：
文献类型：
--
作者：
Junqi Zhang;Cheng Wang;D. Zang;Mengchu Zhou
学习自动机（LA）是强化学习的强大工具。它的动作概率向量起着两个作用：1）决定它何时收敛，即，它已经使用的总计算预算，以及2）在动作之间分配计算预算以识别最优的一个。这两个相互交织的角色导致了一个问题：计算预算主要用于当前估计的最优动作，因为它的动作概率很高，而不管这样的预算分配是否有助于识别真正的最优动作。这项工作提出了一类新的LA，避免使用其行动概率向量计算预算分配。相反，我们只使用这样的向量，以确定它是否收敛，然后采用最佳的计算预算分配，以最大限度地提高识别真正的最佳行动的概率的方式来完成计算预算的分配。证明了ε-最优性。仿真结果验证了该算法的优越性。学习自动机（LA）是一种重要的学习机制，在自动化系统设计、生物系统、计算机视觉和交通运输等领域都有应用。它根据从环境接收的输入更新其动作概率向量以提高其性能。它作为一个自适应控制器在建模过程中，以及产生适当的控制信号。现有的LAs简单地采用算法来更新它们的动作概率向量，然后使用向量进行序优化和确定计算预算大小。本文将序优化与动作概率向量分离，引入最优计算预算分配，以最大化选择真正最优动作的概率。在五种流行的环境下，与现有的方法相比，该算法的学习效率提高了10.93%~ 65.94%。
A learning automaton (LA) is a powerful tool for reinforcement learning. Its action probability vector plays two roles: 1) deciding when it converges, i.e., total computing budget it has used, and 2) allocating computing budget among actions to identify the optimal one. These two intertwined roles lead to a problem: the computing budget mostly goes to the currently estimated optimal action due to its high action probability regardless whether such budget allocation can help identify the true optimal one or not. This work proposes a new class of LA that avoids the use of its action probability vector for computing budget allocation. Instead we use such vector only to determine if it converges and then employ optimal computing budget allocation to accomplish the allocation of computing budget in a way that maximizes the probability of identifying the true optimal actions. ε-optimality is proven. Simulations verify its advantages over existing algorithms. A learning automaton (LA) represents an important leaning mechanism with applications in automated system design, biological systems, computer vision, and transportation. It updates its action probability vector in accordance with the inputs received from the environment to improve its performance. It acts as an adaptive controller in modeling a process as well as generating appropriate control signals. The existing LAs simply employ heuristics to update their action probability vectors and then use the vectors for ordinal optimization and determining the computing budget size. This work separates ordinal optimization from the action probability vector and introduces optimal computing budget allocation to maximize the probability of selecting the true optimal action. Compared with the state-of-the-art methods in five popular environments, the proposed LA speeds up the learning efficiency ranging from 10.93% to 65.94%.