Learning Automata inaThree-Move Zero-Sum Game
G. Langholz, Emilia Katz · 1979
A modelofa two-automata zero-sum gameis described. Thegameconsists ofarepeated number ofplays; each play isspanned over three moves. Theautomata participating inthe gamehave noprior information about itandplay inamanner similar tothat inwhich humanbeings, whodonotknowthegamematrix, would play thegame.Hence, eachautomaton isinformed ofthe actions ofhisadversaries intheprevious moveandusesthis information tomakehismove.Attheendofeachplay areferee informs theautomata whowonandwholost. Conditions onthepayoff functions, sufficient fortheautomata toobtain thevalue ofthegame with anarbitrarily high probability, arederived fromthesemimartin- gale equations describing thebehavior ofthemodeL I.INTRODUCTION Thenotion oflearning automata operating inarandom envir- onmentabout which they havenoapriori knowledge hasreceived considerable attention intheliterature (1). Foreachpossible action oftheautomaton, theenvironment responds byeither rew- arding orpenalizing theautomaton, reward orpenalty being determined bycertain probabilistic rules. Thus, forexample, the automaton's ability tolearn canbemanifested byoptimizing its expected reward. Automaton games canbeviewed asextending theframework of learning automata inarandom environment. Indeed, thelatter canbetermed agameagainst nature. Various examples ofauto- matongamesareconsidered intheliterature. Krilov andTsetlin (2)andTakeuchi etal.(3) dealt withtwo-automata zero-sum games. Chandrasekaran andChen(4)usedvariable structure stochastic automata withnonlinear reinforcement schemes ina zero-sum game. Viswanathan andNarendra (5) described azero- sumgamebetween alinearly reinforced £-optimal automaton and aconditionally optimal (6) automaton with anonlinear reinforce- mentscheme. Various nonzero-sum gamescanbeclassified as investment andthese wereconsidered byGinsburg etal. (7)andFuandLi(8). Gurgames, (2), (9), (10), canalsobe included inthis category. Allthese games, however, arecharac- terized byhaving onemove; that is, theautomata participating in thegamechoose their strategies simultaneously, andtheplay ter- minates after oneunit oftime. Recently, two-automata zero-sum stochastic gameswithin- complete information wereconsidered in(15),1 andconditions enabling learning automata toconverge totheoptimal pure strategies wereestablished.