Զѧ
AGTA AUTOMATICA SINICA
1999 25 2 Vol.25 No.2 1999





Qѧϰ㷨ڿеӦ1)
ɡ
ժҪQѧϰ㷨WatkinsϢȫɷһǿѧϰ.һµ̽ԣòԺQѧϰ㷨Чһ͵״̬;߿ռĿ.÷ĿƲԺֵģ֪õŲԷǳƽӶ֤ʵQѧϰ㷨һЩϵͳģδ֪Ĺ̿еӦǱ.
ؼʡQѧϰɷ߹̣ƣ״̬;߿ռ䣬̽.
INVENTORY CONTROL USING Q-LEARNING
JIANG Guofei Wu Cangpu
(Department of Automatic Control, Beijing Institute of Technology, Beijing 100081)
AbstractQ-learning is a reinforcement learning method to solve Markovian decision problems with incomplete information. In this paper, we present a novel exploration strategy and use Q-learning method with this strategy to solve a typical inventory control problem with continuous state and decision space. Simulation results are included to show that the optimal policy given by Q-learning can well approximate to the accurate one.
Key wordsQ-learning, Markovian decision problem, inventory control, continuous state and decision space, exploration strategy.
1
Qѧϰ㷨ϢȫɷһЧǿѧϰ.ԴWatkins11989Qѧϰ㷨֤Ժ󣬸㷨ǿѧϰоеõǵձע.ȻĿǰQѧϰ㷨Ӧоܲ˹ܷ棬·12ݡʳϷ3ݵȣʵӦõӺ٣һԸ㷨оҲֻһЩɢ״̬;߿ռ.Ϊֹûм״̬;߿ռӦõӣʵӦϵͳ״̬;.ͨɢ״̬;߿ռ䣬Qѧϰ㷨˳ѧһ͵״̬;߿ռĿ⣬ͬʱԾ߿ռɢпĿϴһµ̽ԣԿƺ֮̽ĳͻЧ.
ȼɷģ£ÿʱ䲽k=1,2,,۲Ϲ̵״̬ΪxkѡakյʱrkʹϵͳתƵһ״̬yk,תƸΪPxk,yk(ak).ĿѰһſƲԣʹ꺯0ܦá1Ϊۿ.
һЩʵУ״̬תƸʺ񱨳δ֪ģϢȫϾҪҶ˹ͷǱҶ˹.ǱҶ˹ַΪֱӷͷֱӷ.ֱӷǲϵͳģͶֱӻڹ۲ֵŲԣ2.Qѧϰ㷨ֱӷ.
һԦУQֵΪ״̬xaԦµıۿۺ͵.

(1)
СѧϰҪתƸʺ񱨳δ֪¹ŲԵQֵ.Ц*ʾŲ.
Qѧϰʵ£ÿʱ䲽k۲쵱ǰ״̬xkѡִпakٹ۲״̬ykܼʱrkȻʽQk-1ֵ

(2)
СkΪѧϰӣ
Watkins1֤ѧϰУkһ£һ(x,a)Ԫ÷(2)εkʱQk(x,a)Ը1Q*(x,a).
2ƼϾ߹ģ
xkǲƷkοʼʱĿukkοʼʱĶ(趩˻)wkkеһRǲƷĲֿ.h(h0)ǵλƷĿ,p(p0)ǵλƷãc(c0)ǵλƷĶ.ٶܵĹӦʱȼʶ󲹣xkȡֵ.ʱɽŻģ£
1)״̬תƹзȷ

(3)
2) wk(k=0,1,)ĸʷֲͬ໥
3) ƵĿѡ񶩻uk(xk)Сָ꺯

(4)
ЦΪۿӣC(u)Ϊ¶庯

(5)
ƷĲֿû(ȡ(3)ʽеԼxk+ukR)Bertsekasף4֤˵pcʱŲΪ

(6)
S*ΪļС㣬ΪG(y)=K+G(S*)yСֵ.
Qѧϰ㷨Ͼ⣬̵֪״̬תƹɣֻҪھ߹ܹ۲⵽ϵͳԪ(xk,uk,r(xk,uk),yk)(xkΪǰ״̬ukΪǰƣr(xk,uk)Ϊϵͳ״̬xkִпukõı꣬ykΪ״̬.)ͨѧϰŲ.ڷУĿģʹʵʹQѧϰṩԪ.ʵӦУQѧϰ㷨ֱӴϵͳ۲Ԫ.
ҪӦQѧϰ״̬;߿ռĿ⣬轫״̬;߿ռɢһϢȫɷ߹.轫״̬ɢNΣx=0,1i,,j,,N;ɢMΣu=0,1,,k,,MӵΪL.wkΪһҪɢ.ͿƳʱr(i,k)=C(k.L)+h max(0,i.L+k.L-wk)+p max(0,wk-i.L-k.L)״̬תƸPij(k)=P(j.Lmax(0,i.L+k.L-wk)(j+1).L).Ȼwkĸʷֲδ֪ģʽеPij(k)ʵҲδ֪.ڷϵͳ״̬ʽ(3)תƲᵽӦĸӵ.ھ߿ռɢΪ˼ӿQѧϰ㷨ٶȺŲԣһµ̽ѡΪ.
3̽
QѧϰʵУж̽5.ΪõBoltzmannֲ̽.ٶʱ䲽kʱ״̬Ϊxk,aA(xk)A(xk)״̬ΪxkʱĿƼ.E(a)=Q(xk,a)aA(xk).¸ѡa

(7)
TΪ¶ӣѧϰж˥.
Boltzmannֲ̽ص㣬һµĻڼֱ̽.ÿʱ䲽k¸ѡa

(8)
Pexp loit(a)ΪBoltzmannֲ̽ʽ(7)ʾ.ʽ(8)еĦ(01)ѡһ̶ֵһ򵥵ķֶκ.ʽ(8)еPexp lore(a)ʽȷ

(9)


(10)
(10)ʽn(xk,a)Ϊʱ䲽kΪֹϵͳ״̬xkִпakĴ.,Ϊ0,£0.m(m0)ѧϰж˥.0Pexp lore(a)1,0Pexp loit(a)1,(8)ʽȻ֤0P(a)1ѧϰ̵ĳʼ׶ΣԪaA(xk)ʽ(7)е¶Tʽ(10)еĲmԽPexp loit(a)ֲԽȶPexp lore(a)ķֲԽв죬ʱϵͳҪPexp lore(a)ѡΪӶ֤̽ͻȡֿƾ.ѧϰĽУTm˥aA(xk),Eexp lore(a)ֵһ£ӶʹEexp loit(a)ֲԽвEexp lore(a)ķֲԽΪȣʱƾEexp loitڿΪaѡö̽Eexp lore𽥼ãӶпƾú͸ϵͳ.ѧϰĽһУm,T㣬aA(xk)ΪA(xk)пƵĸʱϵͳҪPexp loit(a)ѡΪӶÿƾͱ֤㷨ٶ.m,Tʱ̽ʵѱһȷֲ̽ԸֵΪѡӦQֵĿƣԸֵΪ1-ȵппнѡѧϰ̵׶һܱ֤㷨ٶȣһҲȻ˶Իһ̽Ų.
4漰
ڷʵУƷĲֿR=100.0λƷĿh=1.0,λƷp=9.0λƷĶc=2.0̶K=0.0.ۿӦ=0.90.wk(50102)ֲ̬.ģ֪ʱ״̬ƷֱɢN=M=50ΣӵΪL=2.0ֵŲͼ1ʾ.ͬʱģδ֪ʱ״̬ƷֱɢN=M=25ΣӵΪL=4.0.QѧϰµĻڼ̽ھ15.9εĿƲͼ2ʾƲԿͼ1ʾŲ.QѧϰBoltzmannֲ̽ھ32.4εĿƲͼ3ʾ÷ھǧεȻȫŲ.ͼ1-3u(x)ʾƲԣxʾ״̬.

ͼ1ͼ2ͼ3
עͼ1 ģ֪ʱֵŲԡN=M=50 L=2.0
ͼ2 ģδ֪ʱQѧϰ㷨µ̽ĿƲԡN=M=25 L=4.0
ͼ3 ģδ֪ʱQѧϰ㷨Boltzmannֲ̽ĿƲԡN=M=25 L=4.0.
Ƚͼ1ͼ2֪Qѧϰ㷨õĿƲԺģֵ֪ŲԷǳƽΪ(6)ʽʾS*ԣS*ԼΪ60.0.ҷͨQѧϰļͼ2ʾĿƲԿŲ.һ˵ϵͳģδ֪£ͨɢ״̬;߿ռ䣬Qѧϰ㷨ĳЩ״̬;߿ռϾŲ.ͬʱͨȽͼ2ͼ3֪µ̽ԺBoltzmannֲ̽ȣѧϰٶȶĿƲԸƽŽŽ.
5
Qѧϰ㷨ص̽һµ̽ԲòԺQѧϰ㷨Чһ͵״̬;߿ռĿ.÷ĿƲԺֵģ֪õŲԷǳƽӶ֤ʵQѧϰ㷨һЩϵͳģδ֪Ĺ̿еӦǱ.
1) ȻѧĿ.
߼飺ɡ19711993ҵڱѧԶϵ.Ϊѧʿ.ҪоſƺܿƵ.
֡206.
ߵλѧԶϵ100081
ο
1Watkins C J C H. Learning from delayed rewards. Ph.D.Dissertation, King's College, UK, 1989
2Barto A G, Bradtke S J, Singh S P. Learning to act using real-time dynamic programming. Artificial Intelligence, 1995, 72: 81-135
3Lin L J. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 1992, 8: 293-321
4Berstekas D P. Dynamic Programming and Stochastic Control.New York Academic Press,1976
5Thrun S B. The role of exploration in learning control. Handbook of Intelligent Control: Neural, Fuzzy and Adaptive Approaches. NYVanostrand Reinhold,1992
6Sutton R S, Barto A G, Williams R J. Reinforcement learning is direct adaptive optimal control. IEEE Control System Magazine, 1992, 12(2):19-22
7Peng J. Efficient dynamic programming-based learning for control. Ph.D.thesis, Northeastern University, USA, 1993
ոڡ1997-04-14
޸ĸڡ1997-11-10
