A Complexity Analysis of Cooperative Mechanisms in Reinforcement Learning
A Complexity Analysis of Cooperative Mechanisms in Reinforcement Learning
复制标题
DOI：
--
复制
发表时间：
1991-07
期刊：
影响因子：
--
通讯作者：
S. Whitehead
中科院分区：
文献类型：
--
作者：
S. Whitehead
当用于解决多阶段决策问题时，强化学习算法执行一种在线（增量）搜索以找到最优决策策略。这种搜索的时间复杂度很大程度上取决于状态空间的大小和结构，以及学习器初始参数值中编码的先验知识。当先验知识不可用时，搜索是公正的，可能是过度的。合作机制通过为学习者提供更短的延迟反馈和辅助经验来源来减少搜索。这些机制是基于这样的观察：在自然界中，智能主体存在于一个合作的社会环境中，帮助组织和指导学习。在这种情况下，学习既包括信息传递，也包括通过试错发现。本文描述了两种合作机制：通过外部批评学习（LEC）和通过观察学习（LBW）。分析了这些算法的搜索时间复杂度，以及无偏q -学习在有限状态空间上的问题解决任务。结果表明，虽然无偏搜索在状态空间大小上需要适度指数级的时间，但LEC和LBW算法在状态空间大小上最多需要线性的时间，并且在适当的条件下，完全独立于状态空间大小；所需的时间与最优解路径的长度成正比。虽然这些分析结果只适用于有限类别的任务，但它们揭示了一般强化学习中搜索的复杂性以及减少搜索的合作机制的效用。
Reinforcement learning algorithms, when used to solve multi-stage decision problems, perform a kind of online (incremental) search to find an optimal decision policy. The time complexity of this search strongly depends upon the size and structure of the state space and upon a priori knowledge encoded in the learners initial parameter values. When a priori knowledge is not available, search is unbiased and can be excessive. Cooperative mechanisms help reduce search by providing the learner with shorter latency feedback and auxiliary sources of experience. These mechanisms are based on the observation that in nature, intelligent agents exist in a cooperative social environment that helps structure and guide learning. Within this context, learning involves information transfer as much as it does discovery by trial-and-error. Two cooperative mechanisms are described: Learning with an External Critic (or LEC) and Learning By Watching (or LBW). The search time complexity of these algorithms, along with unbiased Q-learning, are analyzed for problem solving tasks on a restricted class of state spaces. The results indicate that while unbiased search can be expected to require time moderately exponential in the size of the state space, the LEC and LBW algorithms require at most time linear in the size of the state space and under appropriate conditions, are independent of the state space size altogether; requiring time proportional to the length of the optimal solution path. While these analytic results apply only to a restricted class of tasks, they shed light on the complexity of search in reinforcement learning in general and the utility of cooperative mechanisms for reducing search.