یادگیری تقویتی و Q Learning

/
/
/

یادگیری تقویتی (Reinforcement Learning یا به طور خلاصه RL) یک روش تعاملی است و با روش های یادگیری با نظارت تفاوت دارد. در روش های با نظارت مانند ماشین بردار پشتیبان یا درخت تصمیم برچسب کلاس ها در فاز آموزش تعیین می شود ولی در اینجا بحث یادگیری مطرح است یعنی عامل یا ایجنت باید خود یاد بگیرد. یادگیری نه کلاسترینگ است و نه دسته بندی و در کل روش متفاوتی است. همه روش های یادگیری با ناظر مانند ماشین بردار پشتیبان، بیزین و.. روش یادگیری مشابهی دارند. یعنی یک فاز آموزش دارند که به کمک داده های آموزشی مدل را می سازند و سپس یک فاز تست که با توجه به آنچه یاد گرفته شده داده تست را دسته بندی می کنند. این روش برای کلیه مسائل و بازی هایی که دنباله تصمیم در آنها مهم باشد مانند شطرنج و یادگیری فضای maze توسط عامل و برنامه ریزی ربات ها مثلا ربات های تمیز کننده کارایی دارد. با این روش agent یاد می گیرد که چگونه از state  ای که حرکت خود را آغاز کرده خود را به Goal یا حالت هدف برساند و در هر state بهترین Action کدام است. هدف پیدا کردن کوتاه ترین مسیر و بهترین مسیر برای رسیدن از مبدا به Goal است. این کار بصورت پویا انجام می شود یعنی نیازی نیست که فضای مسئله ثابت باشد بلکه فضای مسئله در حین اجرا می تواند تغییر کند.  به عنوان مثال اگر سر راه ربات یک دیوار قرار گیرد باز هم می تواند مسیر خود را به سمت هدف پیدا کند. این نوع یادگیری در رباتیک کاربرد زیادی دارد چون ربات دقیقا یاد می گیرد که در هر state بهترین action کدام است. در مسائل مربوط بهresource allocation در سیستم عامل و کنترل هلی کوپتر بدون سر نشین هم یادگیری تقویتی کاربرد دارد. این روش، یک روش تعاملی است و یادگیری با سعی و خطا اضافه می شود یعنی عامل یادگیرنده دانش خود را بصورت سعی و خطا از تعامل با محیط می گیرد. Agent در محیط قرار گرفته یک Action انجام می دهد، response ای از محیط می گیرد و طبق آن پاسخ می فهمد عملی که انجام داده خوب بوده یا خیر. Action در واقع عمل هایی است که عامل مجاز است انجام دهد در مثال یادگیری فضای maze توسط ایجنت که در ادامه توضیح داده خواهد شد، حرکت به بالا، پایین، چپ و راست عمل یا اقدام یا Action هستند. یادگیری تقویتی nondeterministic (غیر قطعی) و احتمالاتی است. ایجنت به ازای هر action یک پاداش می گیرد. هرچه پاداش بهتر باشد یعنی عملی که انجام شده بهتر بوده است. هدف نهایی عامل این است که بیشترین پاداش را جمع کند بنابراین خانه هدف یا Goal باید بیشترین پاداش را داشته باشد.

اجزای یادگیری تقویتی

۱- policy
شیوه رفتار agent را در زمان داده شده تعریف می کند. یعنی policy می گوید در هر حالت کدام عمل بهتر است.

۲- تابع پاداش
هدف را در تابع یادگیرنده تعیین می کند. این تابع هدفش این است که به ازای هر عمل عامل یک پاداش بدهد پس به هدف که نزدیک می شود پاداش بیشتر می شود. تابع پاداش مهم است اگر بد تعریف شود عامل دیر یاد می گیرد. Reward کوتاه مدت و value بلند مدت است یعنی ممکن است یک خانه پاداش نداشته باشد ولی ما را به هدف نزدیک تر کند پس value بالاتری دارد.

۳- value function
نگاه بلند مدت دارد. برای هر حالت یک مقدار تعیین می کند که هر چه بیشتر باشد یعنی به هدف نزدیک تر شده ایم. مانند اینکه در یک بازی اجازه دهید حریف مهره شما را بزند در این حالت پاداش نمی گیرید ولی به حالت دیگری می روید که بهتر است این یعنی نگاه بلند مدت.

۴- مدل
اختیاری است. در ابتدا نمی دانیم احتمال اینکه از حالتی به حالت دیگر برویم چقدر است.
مسئله یادگیری تقویتی احتمالاتی و stocastic است و State ها یا حالات آن nondeterministic می باشد. یعنی به ازای یک عمل می تواند به همه حالات برود ولی با یک احتمال. هر عمل یا action یک احتمال است و رفتن از یک حالت به حالت دیگر هم احتمال است. هدف یادگیرنده ماکزیمم کردن پاداش بلند مدت می باشد.
در یک مسئله یادگیری تقویتی با عاملی روبرو هستیم که از طریق سعی و خطا با محیط تعامل کرده و یاد میگیرد تا عملی بهینه را برای رسیدن به هدف انتخاب نماید.
یادگیری تقویتی از اینرو مورد توجه است که راهی برای آموزش عاملها برای انجام یک عمل از طریق پاداش و تنبیه است بدون اینکه لازم باشد نحوه انجام عمل را برای عامل مشخص نماید.
یادگیری تقویتی از دو جنبه با یادگیری با ناظر تفاوت دارد:
مثالهای یادگیری بصورت زوج  (ورودی/ خروجی)  مطرح نمیشوند . بلکه بعد از اینکه عامل عملی را انجام داد پاداشی را دریافت میکند و به مرحله بعدی میرود. عامل هیچ گونه اطلاعی در مورد اینکه در هر حالت بهترین عمل چیست ندارد. بلکه این وظیفه عامل است که در طول زمان تجربه کافی در مورد حالتها، عمل های ممکن، انتقال و پاداش جمع آوری نموده و عملکرد بهینه را یاد بگیرد.
در یادگیری با نظارت، یادگیری از نمونه هایی انجام می شود که توسط یک ناظر خارجی آگاه فراهم شده است. این نوع یادگیری که در مورد آن در مقاله های دیگر در این ماهنامه بحث کرده ایم یادگیری بسیار مهمی است ولی به تنهایی برای یادگیری از تعاملات کافی نیست. در مسائل تعاملی معمولا بدست آوردن مثال هایی از رفتار مورد انتظار  عامل که هم صحیح باشد و هم نشان دهنده همه موقعیت هایی باشد که عامل یا همان ایجنت باید در آن عمل کند، عملی نیست.
در قلمروهای ناشناخته که در آنها انتظار یادگیری مفید می رود عامل باید قادر باشد از تجربه خود یاد بگیرد.
یکی از چالش هایی که در یادگیری تقویتی وجود دارد و در سایر انواع یادگیری وجود ندارد trade off یا تعاملی است که میان exploration و exploitationوجود دارد. exploration یا کاوش موارد جدید یعنی بگذاریم عامل خود کشف کند و یاد بگیرد و  exploitationیعنی عامل از دانش قبلی استفاده نماید. برای به دست آوردن پاداش زیاد agent عمل هایی که قبلا امتحان کرده و آنها را در تولید پاداش موثر دیده ترجیح می دهد. ولی برای کشف این Action ها باید عمل هایی که قبلا انتخاب نکرده را امتحان کند. یعنی باید از آنچه می داند استخراج کند تا پاداش بگیرد ولی مجبور است برای انتخاب Action های بهتر اکتشاف هم انجام دهد. مشکل اینجاست که نه اکتشاف و نه بهره برداری از دانش قبلی بدون شکست خوردن در task نمی تواند دنبال شود. عامل باید انواع مختلفی از Action ها را امتحان کند و آنهایی را که بهتر بوده اند بیشتر در نظر بگیرد. در task های stochastic هر عمل باید بارها امتحان شود تا به تخمین قابل اعتمادی از پاداشی که انتظار دارد برسد. این مبحث تبادل و موازنه میانexploration و exploitation در یادگیری با نظارت مطرح نمی شود.
تفاوت دیگر در اینجاست که سیستم باید کارائی آنلاین بالائی داشته باشد. زیرا اغلب ارزیابی سیستم با  عمل یادگیری بطور همزمان صورت می پذیرد.
بنابراین به طور خلاصه می توان گفت که هدف در یادگیری تقویتی جمع کردن حداکثر پاداش ممکن است؛ حالت بعدی از روی عمل فعلی تعیین میشود؛ یادگیری مبتنی بر سعی و خطاست؛ به ایجینت گفته نمی شود که چه عملی را باید انجام دهد؛ جستجو بر اساس سعی و خطا انجام میشود؛ عامل یادگیرنده سعی میکند اعمالی را یاد بگیرد که بیشترین پاداش را تولید می کنند؛ پاداش از نوع تاخیری است: از اینرو دست آوردهای کوتاه مدت فدای مزایای بلند مدت تر میشوند؛ باید بین کاوش موارد جدید و استفاده از دانش قبلی تناسب ایجاد نمود.
در RLوقتی عامل  در یک حالت خاص عملی را انجام میدهد، در مقابل پاداش (reward or reinforcement)  دریافت میکند. در این سیستم، عامل وظیفه دارد تا پاداش دریافتی در دراز مدت را حداکثر نماید.

الگوریتم یادگیری Q
یادگیری Q یک تکنیک یادگیری تقویتی است که با یادگیری یک تابع اقدام/مقدار، سیاست مشخصی را برای انجام حرکات مختلف در وضعیت های مختلف دنبال می کند. یکی ازنقاط قوت این روش، توانایی یادگیری تابع مذکور بدون داشتن مدل معینی ازمحیط می باشد.
در اینجا مدل مسئله از یک ایجنت، وضعیت ها ( S ) و مجموعه ای از اقدامات ( A ) برای هر وضعیت تشکیل شده است. با انجام یک اقدام  ، ایجنت از یک وضعیت به وضعیت بعدی حرکت کرده و در هر وضعیت پاداشی به ایجنت می دهد. هدف ایجنت حداکثر کردن کل پاداش دریافتی خود است. این کار با یادگیری اقدام بهینه برای هر وضعیت انجام می گردد. الگوریتم دارای تابعی است که ترکیب state/action را محاسبه می نماید .
قبل از شروع یادگیری،Q مقدار ثابتی را که توسط طراح انتخاب شده برمی گرداند. سپس هر بار که به ایجنت پاداش داده می شود، مقادیر جدیدی برای هر ترکیب state/action محاسبه می گردد. هسته الگوریتم از یک بروز رسانی تکراری ساده تشکیل شده است. به این ترتیب که بر اساس اطلاعات جدید مقادیر قبلی اصلاح می شود.
یک اپیزود الگوریتم وقتی عامل به وضعیت نهایی یعنی هدف می رسد پایان می یابد.
نرخ یادگیری تعیین می کند که تا چه میزان اطلاعات بدست آمده جدید بر اطلاعات قدیمی ترجیح داده شود. مقدار صفر باعث می شود ایجنت چیزی یاد نگیرد و مقدار یک باعث می شود ایجنت فقط اطلاعات جدید را ملاک قرار دهد.
عامل تخفیف، اهمیت پاداش های آینده را تعیین می کند. مقدار صفر باعث می شود ایجنت ماهیت فرصت طلبانه (shortsighted یا کوتاه مدت) گرفته و فقط پاداش های فعلی را مد نظر قرار می دهد. در حالی که مقدار یک، ایجنت را ترغیب می کند دوره زمانی طولانی تری برای پاداش تقلا کند. اگر این عامل، یک یا بیشتر از یک باشد مقادیر   واگرا می شود.
در ساده ترین شکل یادگیری کیو از جداول برای ذخیره داده استفاده می شود. این روش با پیچیده شدن سیستم مورد نظر، به سرعت کارایی خود را از دست می دهد.
Q-learning نوعی از یادگیری تقویتی بدون مدل است که بر پایه برنامه ریزی پویای اتفاقی عمل میکند.
در یادگیری Q بجای انجام یک نگاشت از ‏Stateها به مقادیر حالتها، نگاشتی از زوج state/action به مقادیری که Q-value نامیده میشوند انجام میگردد.

Q-Function
به هرزوج > حالت ، عمل<  یک مقدار Q(s,a) نسبت داده میشود. این مقدار عبارت است از مجموع پاداشهای دریافت شده وقتی که از حالت S شروع کرده و عمل a را انجام داده و بدنبال آن خط مشی (سیاست یا policy) موجود را دنبال کرده باشیم.
همان طور که پیش تر گفته شد، برای یادگیری تابع Q میتوان از جدولی استفاده کرد که هر ورودی آن یک زوج <s,a> به همراه تقریبی است که یادگیر از مقدار واقعی Q بدست آورده است.
مقادیر این جدول با مقدار اولیه تصادفی ) معمولا صفر(  پر می شود.
عامل بطور متناوب وضعیت  فعلی S را تشخیص داده و عملی مثل a را انجام می دهد. سپس پاداش حاصله r(s,a)  و همچنین حالت جدید ناشی از انجام عمل s’=d(s,a)  را مشاهده می کند.
مقادیر جدول با استفاده از رابطه زیر تغییر می کنند:
از آنجائیکه در محیط، یک حالت هدف در نظر گرفته میشود که با رسیدن عامل به آن حالت، حرکت عامل متوقف میشود، عمل یادگیری بصورت اپیزودی انجام میشود.
در هر اپیزود عامل در یک محل تصادفی قرار داده میشود و تا رسیدن به حالت هدف به تغییر مقادیر Q ادامه میدهد وقتی به هدف برسد اپیزود تمام می شود و یک اپیزود جدید شروع می شود.
اگر مقادیر اولیه Q  صفر در نظر گرفته شده باشند، در هر اپیزود فقط یکی از مقادیر که به مقدار نهائی نزدیکتر هستند تغییر کرده و بقیه صفر باقی می مانند. با افزایش تکرار اپیزود ها این مقادیر غیر صفر به سایر مقادیر جدول گسترش پیدا کرده و درنهایت به مقادیر بهینه همگرا خواهند شد. در یادگیری Q از اختلاف بین مقدار حالت فعلی و حالت بعد از آن استفاده می شود. این امر را میتوان به اختلاف بین حالت فعلی و چند حالت بعدی تعمیم داد.
محمد محمدنژاد
اجرای کد MATLAB مربوط به یادگیری عامل در فضای maze با الگوریتم یادگیری Q:
در زیر توابع مربوط به اجرای الگوریتم یادگیری کیو در فضای maze در MATLAB آورده شده که هر یک از این توابع جهت درک و تفکیک بهتر در یک فایل .m جداگانه ذخیره شده اند. در نهایت نیازی به اجرای تک تک این توابع نبوده و با اجرای فایل main.m الگوریتم اجرا می شود و با توجه به تعداد تکرارهایی که برای آن تعریف شده اپیزودها را تکرار می کند. در ادامه برای نمونه چند تابع اجرا شده و نتیجه نمایش داده شده است.
function [ Model ] = BuildModel( nstates,nactions )
Model = zeros(nstates,nactions,2);
function [ actions ] = BuildActionList
actions = [1 ; 2 ; 3 ; 4];
function [ Q ] = BuildQTable( nstates,nactions )
Q = zeros(nstates,nactions);
function [ states ] = BuildStateList(N,M)
x1  = ۰:N-1;
x2  = ۰:M-1;
states = setprod(x1,x2);
end
function CreateFigureGrid(N,M)
figure1 = figure();
% Create axes
axes1 = axes(‹Parent›,figure1,›YTick›,۰:M,›YGrid›,›on›,…
‹XTick›,۰:N,…
‹XGrid›,›on›,…
‹XTickLabel›,[],…
‹YTickLabel›,[],…
‹Position›,[۰٫۱۳۶۸ ۰٫۱۱۵۳ ۰٫۷۷۵ ۰٫۸۱۵],…
‹PlotBoxAspectRatio›,[N M 1],…
‹GridLineStyle›,›-›,…
‹DataAspectRatio›,[۱ ۱ ۱]);
% Uncomment the following line to preserve the X-limits of the axes
xlim(axes1,[0 N]);
% Uncomment the following line to preserve the Y-limits of the axes
ylim(axes1,[0 M]);
box(axes1,›on›);
hold on
text(0.3,0.5,›S›,›FontName›,›Courier New›);
text(5.3,5.5,›G›);
function [ maze,nrows,ncols ] = CreateMaze()
nrows = 9;
ncols = 6;
% Maze base
maze = zeros(nrows,ncols);
%Add some obstacles as ones in the maze
maze(3,3:5) =1;
maze(6,2)   =۱;
maze(8,4:6) =1;
end
function [ pos ] = DediscretizeState( s, maze )
[N M] = size(maze);
ss = s-1;
pos = [fix(ss/M) mod(ss,M)];
end
function [ s ] = DiscretizeState( x, statelist )

[d  s] = min(dist(statelist,x›));
function [ posp ] = DoAction( action, pos,maze )
x = pos(1);
y = pos(2);
[N M] = size(maze);
% bounds for x
xmax = N-1;
xmin = 0;
% bounds for y
ymax = M-1;
ymin = 0;
if (action==1)
y = y + 1;
elseif (action==2)
x = x + 1;
elseif (action==3)
y = y – 1;
elseif (action==4)
x = x – 1;
end
x = min(xmax,x);
x = max(xmin,x);

y = min(ymax,y);
y = max(ymin,y);
if maze(x+1,y+1)==1
x = pos(1);
y = pos(2);
end
posp=[x y];
function [ sp, r, terminal ] = DoActionFromSimulatedModel( Model, s, a, statelist, actionlist )
sp = Model(s,a,1);
r = Model(s,a,2);
terminal = 0;
if(sp == 0)
terminal = -1;
end
if(sp == 54)
terminal = 1;
end
function [ a ] = e_greedy_selection( Q , s, epsilon )
% e_greedy_selection selects an action using Epsilon-greedy strategy
% Q: the Qtable
% s: the current state
nactions = size(Q,2);
if (rand()>epsilon)
a = GetBestAction(Q,s);
else
% selects a random action based on a uniform distribution
% +۱ because randint goes from 0 to N-1 and matlab matrices goes from
% ۱ to N
a = randi(nactions);
end
function [ d ] = edist( x , y )
%edist euclidean distance between two vectors
d = sqrt( sum( (x-y).^2,2 ) );
function [ total_reward,steps,Q,Model ] = Episode( maxsteps, Q,Model , alpha, gamma,epsilon,statelist,actionlist,grafic,maze,start,goal,p_steps )
x            = start;
steps        = ۰;
total_reward = 0;
nstates     = size(statelist,1);
nactions    = size(actionlist,1);
Qt           = BuildQTable(nstates,nactions );
% convert the continous state variables to an index of the statelist
s   = DiscretizeState(x,statelist);
% search from s0
Qt   = SearchWithDPVI(s, Q, Qt, Model, epsilon, alpha, gamma, maxsteps, statelist, actionlist);
% selects an action using the epsilon greedy selection strategy
a   = e_greedy_selection(Qt,s,epsilon);
for i=1:maxsteps
% convert the index of the action into an action value
action = actionlist(a);
%do the selected action and get the next agent state
xp  = DoAction( action , x, maze );
% observe the reward at state xp and the final state flag
[r,f]   = GetReward(xp,goal);
total_reward = total_reward + r;
% convert the continous state variables in [xp] to an index of the statelist
sp  = DiscretizeState(xp,statelist);
% update the model
Model = UpdateModel(s,a,r,sp,Model);
% search from current s
Qt =  SearchWithDPVI(sp, Q, Qt, Model, epsilon, alpha, gamma, maxsteps, statelist, actionlist);
% select action prime
ap = e_greedy_selection(Qt,sp,epsilon);
%ap = e_greedy_selection(Q,sp,epsilon);
% Update the Qtable, that is,  learn from the experience
Q = UpdateQLearning( s, a, r, sp, ap, Q, alpha, gamma );
%update the current variables
s = sp;
a = ap;
x = xp;
%increment the step counter.
steps=steps+1;
% save model
save(‹data.mat›, ‹Q›, ‹Model›);
if (grafic==true)
figure(1);
Plot( x,a,steps,maze,start,goal,[‹Rayaneh (N=› num2str(p_steps) ‹)›]);
end
% if reaches the goal breaks the episode
if (f==true)
break
end

end
function [ a ] = GetBestAction( Q, s )
nactions=size(Q,2);
[v idx]    = sort(Q(s,:),›descend›);
x          = diff(v);
i          = find(x,1);
if isempty(i)
a = randi(nactions);
else
% i is the number of equal elements
j = randi(i);
a = idx(j);
end
end
function [ r,f ] = GetReward( pos,goal )
if ( pos==goal )
r = 1;
f = true;
else
r = 0;
f = false;
end
function  MazeDemo( maxepisodes )
clc
start       = [۰ ۳];
goal        = [۸ ۵];
[maze N M]  = CreateMaze();
statelist   = BuildStateList(N,M);  % the list of states
actionlist  = BuildActionList(); % the list of actions

nstates     = size(statelist,1);
nactions    = size(actionlist,1);

%Generate initial Population
Q           = BuildQTable(nstates,nactions ); % the Qtable
Model       = BuildModel(nstates,nactions ); % the Qtable
% planning steps
p_steps     = ۵۰;
maxsteps    = ۲۰۰۰;  % maximum number of steps per episode
alpha       = ۰٫۱;   % learning rate
gamma       = ۰٫۹۵;  % discount factor
epsilon     = ۰٫۱;   % probability of a random action selection
grafica     = false; % indicates if display the graphical interface
grafica     = true;
xpoints=[];
ypoints=[];
for i=1:maxepisodes
[total_reward,steps,Q,Model ] =  Episode( maxsteps, Q, Model , alpha, gamma,epsilon,statelist,actionlist,grafica,maze,start,goal,p_steps ) ;
disp([‹Espisode: ‹,int2str(i),›  Steps:›,int2str(steps),›  Reward:›,num2str(total_reward),› epsilon: ‹,num2str(epsilon)])

xpoints(i)=i-1;
ypoints(i)=steps;
subplot(2,1,2);
plot(xpoints,ypoints)
title([‹Episode: ‹,int2str(i),› epsilon: ‹,num2str(epsilon)])
drawnow
if (i>2000000)
grafica=true;
end
end
function Plot( x,a,steps,maze,start,goal, ptitle )
[N M] = size(maze);
subplot(2,1,1);
% Agent
plot(x(1)+0.5,x(2)+0.5,›sk›,›MarkerFaceColor›,›k›,›MarkerSize›,۱۰);
title(ptitle);
% Create axes
set(gca,›YTick›,۰:M,›YGrid›,›on›,…
‹XTick›,۰:N,…
‹XGrid›,›on›,…
‹XTickLabel›,[],…
‹YTickLabel›,[],…
‹PlotBoxAspectRatio›,[N M 1],…
‹GridLineStyle›,›-›,…
‹DataAspectRatio›,[۱ ۱ ۱]);
% Uncomment the following line to preserve the X-limits of the axes
xlim(gca,[0 N]);
% Uncomment the following line to preserve the Y-limits of the axes
ylim(gca,[0 M]);
box(gca,›on›);
hold on
text(start(1)+0.3,start(2)+0.5,›S›,›FontName›,›Courier New›);
text(goal(1)+0.3,goal(2)+0.5,›G›,›FontName›,›Courier New›);
[mx my] = find(maze);
plot(mx-0.5,my-0.5,›s›,›MarkerEdgeColor›,[.۵ .۵ .۵],›MarkerFaceColor›,[.۵ .۵ .۵],›MarkerSize›,۲۰);
drawnow
hold off
function Q = RandomPlanning(Q, Model, steps, alpha, gamma )
[s_list a_list] = find(Model(:,:,1));
for j=1:steps
%random index over s_list
i = randi(numel(s_list));
% random previously visited state
s = s_list(i);
% random action previously taken at state s
a = a_list(i);
sp  = Model(s,a,1);
r   = Model(s,a,2);
Q      = UpdateQLearning( s, a, r, sp, [], Q , alpha, gamma );
end
end

function [ Qt ] = Search( start, Q, Qt, Model, epsilon, alpha, gamma, maxsteps, statelist, actionlist )
for i=1:10
s = start;
a   = e_greedy_selection(Qt,s,epsilon);
steps = 0;
for j=1:maxsteps
[sp, r, terminal] = DoActionFromSimulatedModel(Model, s, a, statelist, actionlist);
if(terminal == -1)
break
end
ap = e_greedy_selection(Qt,s,epsilon);
% update short term Q
Qt     = UpdateSimulatedQLearning(s, a, r, sp, ap, Q, Qt, alpha, gamma);
s = sp;
a = ap;
steps = steps+1;
if(terminal == 1)
break
end
end
end

end
function [ Qt ] = SearchWithDPVI( start, Q, Qt, Model, epsilon, alpha, gamma, maxsteps, statelist, actionlist )

for i=1:10
s = start;
a   = e_greedy_selection(Qt,s,epsilon);
steps = 0;
for j=1:maxsteps
[sp, r, terminal] = DoActionFromSimulatedModel(Model, s, a, statelist, actionlist);
if(terminal == -1)
break
end
actionCount = size(actionlist, 1);
Qtt = zeros(1, actionCount);
for k=1:actionCount
Qtt(k) = Qt(sp, k);
end
Qt(s,a) = r + gamma * max(Qtt);
ap = e_greedy_selection(Qt,s,epsilon);
s = sp;
a = ap;
steps = steps+1;
if(terminal == 1)
break
end
end
end
end
function C = setprod(varargin)
args = varargin;
if any([cellfun(‹isclass›,args,›cell›) cellfun(‹isclass›,args,›struct›)])
error(‹ SETPROD only supports numeric/character arrays ‹)
end
n = nargin;
[F{1:n}] = ndgrid(args{:});
for i=n:-1:1
G(:,i) = F{i}(:);
end
C = unique(G , ‹rows›);
function [ Model ] = UpdateModel( s, a, r, sp, Model )
Model(s,a,1) = sp;
Model(s,a,2) = r;
function [ Q ] = UpdateQLearning( s, a, r, sp, ap, Q, alpha, gamma )
TD_error =   r + gamma*Q(sp,ap) – Q(s,a);
Q(s,a) =  Q(s,a) + alpha * TD_error;
function [ Qt ] = UpdateSimulatedQLearning( s, a, r, sp, ap, Q, Qt, alpha, gamma )

TD_error =   r + gamma * Qt(sp, ap) – Qt(s, a);
Qt(s,a) =  Qt(s,a) + alpha * TD_error;
end
// main.m
clear all
clc
close all
MazeDemo(9);

نتیجه اجرای فایل main.m برای ۹ اپیزود:
نتیجه اجرا در ۶۰ اپیزود:
در شکل فوق می توان مشاهده کرد که عامل در هر اپیزود چند گام طی کرده و با گرفتن پاداش اپیزود به اتمام رسیده است.
همان طور که در تابع function  MazeDemo( maxepisodes ) مشاهده می شود تعداد اپیزودها در این تابع تعریف شده که در فایل main.m فراخوانی شده و مقدار دلخواه را به آن می دهیم. نکته دیگری که درباره این تابع باید گفت این است که مقادیر آلفا (نرخ یادگیری)، گاما (نرخ تخفیف)، اپسیلون (احتمال انتخاب یک عمل تصادفی) و تعداد گام های هر اپیزود در این تابع یعنی MazeDemo تعیین می شود. مقدار متداول برای ضریب یادگیری ۰٫۱ است در این مثال نیز با همین ضریب اجرا کرده ایم ولی در صورت تمایل می توانید ضریب یادگیری را تغییر دهید و تغییر رفتار عامل در یادگیری و افزایش یا کاهش یادگیری کامل را با ایجاد تغییر در ضریب یادگیری مشاهده نمایید. ضمنا در مثال های اجرا شده مقدار اپسیلون نیز ۰٫۱ در نظر گرفته شده است.
ضریب یادگیری زیاد و نزدیک به یک باعث کند شدن یادگیری عامل می شود. زیرا عامل به یادگیری هایی که از هر مرحله به دست آورده توجهی نکرده و فقط به یادگیری های جدید توجه می کند بنابراین همگرایی دیرتر صورت می گیرد. اینکه در نهایت عامل می تواند یاد بگیرد به این خاطر است که این ضریب یادگیری طبق ماهیت الگوریتم یادگیری Q به صفر همگرا شده و کم کم کاهش پیدا می کند بنابراین در آخر کار یادگیری تسریع می شود.
ضریب یادگیری ارتباط بین حافظه قدیم و جدید را توصیف میکند. مقدار بالای آن نشان دهنده این است که اطلاعات جدید (حافظه جدید) بر حافظه قدیم ارجحیت دارد. ضریب یادگیری می گوید که Action های آتی چقدر باید مورد توجه قرار گیرند. ضریب یادگیری یک می گوید تنها اطلاعات خیلی جدید در نظر گرفته شود. نرخ یادگیری بالاتر در ابتدای امر بد نیست ولی در انتها مقدار کمتر بهتر است.
ضریب یادگیری بالاتر در ابتدا منحنی یادگیری با شیب بیشتری ایجاد می کند زیرا هدف این پارامتر همین است. نتایج نهایی اغلب با نرخ یادگیری پایین تر بهتر است. احتمالا به این دلیل که هنگام استفاده از ضریب یادگیری بالاتر تجربیات قدیمی خیلی زود با تجربیات جدید جایگزین می شوند و یادگیری را مختل می کنند که به این معنی است که عامل یادگیرنده حافظه خوبی ندارد. برای نتایج نهایی خوب یک نرخ یادگیری نسبتا پایین بهتر است. نرخ یادگیری بالاتر برای شروع کار بهتر است. ولی در کل استفاده از نرخ های یادگیری پایین تر نتایج بهتری در بر دارد. یعنی مثلا نرخ یادگیری ۰٫۸ نتایج کوتاه مدت بدی نداشته ولی نرخ یادگیری مثل ۰٫۲ نتایج بلند مدت بهتری دارد. الگوریتم یادگیری Q نسبت به الگوریتم سارسا کندتر همگرا می شود ولی قابلیت این را دارد که همزمان با تغییر policyها به یادگیری ادامه دهد.

————-

هدی ابیضی

2 نظرات

  1. سلام من یه برنامه q-learning می خوام برای بازار برق بنویسم ولی در نوشتنش دچار مشکلم.در واقع در آپدیت کردن Q مشکل دارم.این بازار یه حالت(satate)ویک عمل(action) دارهکه قیمتا از یک تا سی با گام یک تغییر می کنند تابع پاداش هم مقدار فروشمون که ضرب قیمت در یه عدد ثابت مثلا ۱۰۰ می باشد اگه کدی در این ارتباط دارید ممنون میشه واسم بفرستید
    پپ

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

It is main inner container footer text