学习自动机

学习自动机（learning automaton）是一种1970年代就开始研究的机器学习算法。学习自动机是由对以往对环境的经验来选择目前的动作。若环境是随机性的，且使用了马可夫决策过程，则这种学习自动机属于强化学习的算法。

历史

学习自动机的研究可以追溯到苏联的Michael Lvovitch Tsetlin在1960年代所做的研究。他和同事们发表了数篇论文，说明如何用矩阵来描述自动机功能。此外，Tsetlin也在研究合理及集体性的自动机行为，以及自动机游戏的。美国学者在1960年代也有探讨学习自动机。不过一直到1974年Narendra及Thathachar在一调查报告中才开始使用“learning automaton”此一名词。

定义

学习自动机是在一随机环境下的适应性决策产生单元，可以根据和环境重复的互动来学习最佳的动作。动作是依照特定的几率分布来决定，而系统会依采取特定行动后的环境反应来更新几率分布。

在强化学习的领域中，学习自动机的特征是马可夫决策过程。政策迭代者会直接处理π，这点其他强化学习的算法不同。另一个政策迭代者的例子是演化算法。

形式上，Narendra和Thathachar用以下的方式定义随机自动机

• x为可能输入的集合
• Φ = { Φ₁, ..., Φ_s } 是可能内部状态的集合
• a set α = { α₁, ..., α_r } 是可能输出或是动作的集合，r≤s,
• 初始的状态几率向量p(0) = ≪ p₁(0), ..., p_s(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-模型是允许x为区间 [0,1]中的实数为。

有限动作集学习自动机

有限动作集学习自动机（Finite action-set learning automata、FALA）是可能动作数量有限的学习自动机，若用较数学的说法来表示，是动作集合大小为有限值的学习自动机。

相关条目

• 强化学习
• 博弈论
• 自动机理论

文献

• Philip Aranzulla and John Mellor (Home page):
  • Mellor J and Aranzulla P (2000): "Using an S-Model Response Environment with Learnng Automata Based Routing Schemes for IP Networks ", Proc. Eighth IFIP Workshop on Performance Modelling and Evaluation of ATM and IP Networks, pp 56/1-56/12, Ilkley, UK.
  • Aranzulla P and Mellor J (1997): "Comparing two routing algorithms requiring reduced signalling when applied to ATM networks", Proc. Fourteenth UK Teletraffic Symposium on Performance Engineering in Information Systems, pp 20/1-20/4, UMIST, Manchester, UK.
• Narendra K., Thathachar M.A.L. Learning automata – a survey (PDF). IEEE Transactions on Systems, Man, and Cybernetics. July 1974, SMC–4 (4): 323–334 [2018-09-24]. doi:10.1109/tsmc.1974.5408453. （原始内容存档 (PDF)于2018-07-21）. 
• Mikhail L’vovich TSetlin., Automaton Theory and the Modelling of Biological Systems, New York and London, Academic Press, 1973. (Find in a library（页面存档备份，存于互联网档案馆）)