学习型自动机

学习型自动机是1970年代以来研究的一种机器学习算法。学习型自动机根据环境中过去的经验来选择它们当前的行动。如果环境是随机的，并且使用马尔科夫决策过程（MDP），它将属于强化学习的范围。

学习自动机的研究可以追溯到20世纪60年代初MichaelLvovitchTsetlin的工作。他与一些同事一起，发表了一系列关于如何使用矩阵来描述自动机功能的论文。此外，Tsetlin还研究了合理和集体的自动机行为，以及自动机游戏。

学习型自动机是一个位于随机环境中的适应性决策单元，它通过与环境的反复互动学习最佳行动。

行动是根据特定的概率分布选择的，该概率分布根据自动机通过执行特定行动获得的环境响应而更新。就强化学习领域而言，学习自动机的特点是政策迭代器。与其他强化学习器相比，策略迭代器直接操纵策略π。策略迭代器的另一个例子是进化算法。

从形式上看，Narendra和Thathachar将随机自动机定义为由以下部分组成。一组X的可能输入，一组Φ={Φ1,...,Φs}的可能内部状态，一组α={α1,...,αr}的可能输出，或行动，r≤s，一个初始状态概率向量p(0)=≪p1(0),...,ps(0)...,ps(0)≫，一个可计算的函数A，在每个时间步骤t之后，从p(t)、当前输入和当前状态生成p(t+1)，以及一个函数G。

在他们的论文中，他们只研究了r=s的随机自动机和G是双射的，允许他们混淆动作和状态。

这样的自动机的状态对应于离散状态的离散参数马尔科夫过程的状态。在每个时间步骤t=0,1,2,3,...，自动机从其环境中读取输入，通过A将p(t)更新为p(t+1)，根据概率p(t+1)随机选择一个后续状态并输出相应的动作。

通常使用输入集X={0,1}，0和1分别对应于环境的非惩罚性反应和惩罚性反应；在这种情况下，自动机应该学会使惩罚性反应的数量最小化，自动机和环境的反馈循环被称为P模型。更一般地说，Q模型允许一个任意的有限输入集X，而S模型使用实数的区间[0,1]作为X。

纽卡斯尔大学的微系统（microSystems）研究小组已经开发了一个单一学习自动机的可视化演示/艺术作品。

有限行动集学习自动机（FALA）是一类学习自动机，对它来说，可能的行动数是有限的，或者用更多的数学术语来说，行动集的大小是有限的。