مارا دنبال کنید : 

الگوریتم Q-Learning(بخش سوم)
پیاده سازی الگوریتم Q-Learning در پایتون

مرحله 1: تعریف محیط (Define the Environment)

پارامترهای محیط را تنظیم کنید، از جمله تعداد حالات و اقدامات، Q-table را مقدار دهی اولیه کنید. در این دنیای شبکه‌ای، هر حالت نمایانگر یک موقعیت است و اقدامات عامل را در این محیط جابجا می‌کند.

				
					import numpy as np

# Define the environment
n_states = 16
n_actions = 4
goal_state = 15
# Initialize Q-table with zeros
Q_table = np.zeros((n_states, n_actions))
				
			

مرحله 2: تنظیم هایپرپارامترها (Set Hyperparameters)

پارامترهای الگوریتم Q-Learning را تعریف کنید، از جمله نرخ یادگیری، عامل تخفیف، احتمال کاوش، و تعداد دوره‌های آموزشی.

				
					# Define parameters
learning_rate = 0.8
discount_factor = 0.95
exploration_prob = 0.2
epochs = 1000
				
			

مرحله 3: پیاده‌سازی الگوریتم Q-Learning (Implement the Q-Learning Algorithm)

الگوریتم Q-Learning را در چندین دوره آموزشی اجرا کنید. هر دوره شامل انتخاب اقدامات بر اساس استراتژی ϵ-greedy، به‌روزرسانی مقادیر Q بر اساس پاداش‌های دریافتی، و انتقال به حالت بعدی است.

				
					# Q-learning algorithm
for epoch in range(epochs):
    current_state = np.random.randint(0, n_states)
    while current_state != goal_state:
        if np.random.rand() < exploration_prob:
            action = np.random.randint(0, n_actions)
        else:
            action = np.argmax(Q_table[current_state])
        next_state = (current_state + 1) % n_states
        reward = 1 if next_state == goal_state else 0
        Q_table[current_state, action] += learning_rate * \
            (reward + discount_factor *
             np.max(Q_table[next_state]) - Q_table[current_state, action])
        current_state = next_state
				
			

مرحله 4: خروجی Q-table (Output the Learned Q-Table)

پس از آموزش، Q-table را چاپ کنید تا مقادیر Q یادگرفته‌شده را بررسی کنید که نمایانگر پاداش‌های مورد انتظار برای انجام اقدامات خاص در هر حالت هستند.

				
					print("Learned Q-table:")
print(Q_table)
				
			

مرحله5: خرجی کد

				
					Learned Q-table:
[[0.48767498 0.48751892 0.46816798 0.        ]
 [0.51334208 0.49211897 0.51330921 0.51333551]
 [0.54036009 0.54035317 0.54036003 0.5403598 ]
 [0.56880004 0.56880008 0.56880003 0.56880009]
 [0.59873694 0.59873694 0.59873693 0.59873694]
 [0.63024941 0.63024941 0.63024941 0.63024941]
 [0.66342043 0.66342043 0.66342043 0.66342043]
 [0.6983373  0.6983373  0.6983373  0.6983373 ]
 [0.73509189 0.73509189 0.73509189 0.73509189]
 [0.77378094 0.77378094 0.77378094 0.77378094]
 [0.81450625 0.81450625 0.81450625 0.81450625]
 [0.857375   0.857375   0.857375   0.857375  ]
 [0.9025     0.9025     0.9025     0.9025    ]
 [0.95       0.95       0.95       0.95      ]
 [1.         1.         1.         1.        ]
 [0.         0.         0.         0.        ]]
				
			

الگوریتم Q-Learning شامل آموزش تکراری است که در آن عامل محیط را کاوش کرده و Q-table خود را به‌روزرسانی می‌کند. این فرایند از یک حالت تصادفی شروع می‌شود، اقدامات را از طریق استراتژی ϵ-greedy انتخاب می‌کند و حرکات را شبیه‌سازی می‌کند. یک تابع پاداش به‌ازای رسیدن به حالت هدف، مقدار ۱ را ارائه می‌دهد. مقادیر Q با استفاده از قاعده Q-Learning به‌روزرسانی می‌شوند و پاداش‌های دریافتی و مورد انتظار را ترکیب می‌کنند. این فرایند ادامه می‌یابد تا زمانی که عامل استراتژی‌های بهینه را یاد بگیرد. Q-Learning نهایی نمایانگر مقادیر حالت-عمل به‌دست‌آمده پس از آموزش است.

الگوریتم Q-Learning (بخش دوم)
Q-table چیست؟

Q-table یک ساختار داده‌ای است که جوایز آینده مورد انتظار برای هر جفت اقدام-وضعیت را ذخیره می‌کند و به‌عنوان مخزنی از پاداش‌های مرتبط با اقدامات بهینه برای هر حالت در یک محیط خاص عمل می‌کند. این جدول به‌عنوان راهنمایی برای عامل به‌کار می‌رود و به او کمک می‌کند تا تعیین کند کدام اقدامات احتمالاً بهترین نتایج را به همراه خواهند داشت. با تعامل عامل با محیط، Q-table به‌طور پویا به‌روزرسانی می‌شود تا درک در حال تکامل عامل را منعکس کرده و تصمیم‌گیری‌های آگاهانه‌تری را امکان‌پذیر سازد. جوهره Q-Learning در این جدول نهفته است، زیرا مقادیر Q ناشی از انجام اقدام‌های مختلف در وضعیت‌های مختلف را ذخیره کرده و به بهبود یادگیری عامل کمک می‌کند.

به عنوان مثال:

فرض کنید یک ربات در یک هزارتو قرار دارد و هدف آن رسیدن به یک نقطه خاص (خروجی) است. برای کمک به ربات در یادگیری بهترین راه‌ها برای رسیدن به هدف، از جدول Q (Q-table) استفاده می‌کنیم.

وضعیت‌ها و اقدامات

در این مثال، وضعیت‌های مختلف می‌توانند مکان‌های مختلف ربات در هزارتو باشند، مانند S1 (شروع)، S2 (نزدیک دیوار)، S3 (نزدیکی خروجی)، S4(خروجی). همچنین، اقدامات ممکن برای ربات در هر وضعیت شامل A1 (حرکت به بالا)، A2(حرکت به پایین)، A3(حرکت به چپ)، A4(حرکت به راست).

Q-table 

جدول Q به‌صورت زیر خواهد بود:

وضعیتA1(بالا)A2(پایین)A3(چپ)A4(راست)
S10.20.10.00.4
S20.30.20.10.2
S30.00.40.50.1
S40.00.00.00.0

توضیحات جدول

  • هر سلول در جدول Q نشان‌دهنده مقدار Q برای یک جفت خاص از وضعیت و اقدام است. برای مثال، در وضعیت S1، اگر ربات اقدام A4 (حرکت به راست) را انتخاب کند، انتظار دارد که مقدار پاداشی معادل4 دریافت کند.
  • هر بار که ربات یک عمل را انجام می‌دهد و پاداشی را دریافت می‌کند، مقدار Q مربوط به آن وضعیت و عمل به‌روزرسانی می‌شود. این به ربات کمک می‌کند تا با مرور زمان، یاد بگیرد که کدام اقدامات در هر وضعیت منجر به بیشترین پاداش می‌شوند.

با استفاده از جدول Q، ربات می‌تواند به‌مرور زمان یاد بگیرد که در هر وضعیت بهترین اقدام کدام است تا به هدف (خروجی) برسد. به‌عبارتی، Q-table به ربات کمک می‌کند تا تصمیم‌گیری‌های بهینه‌تری داشته باشد و در نهایت به موفقیت برسد.

مراحل کلیدی الگوریتم Q-Learning
1.مقدمه‌سازی (Initialization): جدول Q با مقادیر دلخواه، معمولاً با صفرها، مقدمه‌سازی می‌شود.

2.کاوش و بهره‌برداری (Exploration and Exploitation): عامل با محیط تعامل می‌کند و اقدام‌هایی را بر اساس جدول Q انجام می‌دهد. این عامل تعادلی بین کاوش (تلاش برای انجام اقدام‌های تصادفی به منظور جمع‌آوری اطلاعات) و بهره‌برداری (انتخاب اقدام‌هایی با بالاترین مقادیر Q به منظور حداکثر کردن جوایز) برقرار می‌کند.

3.انتخاب اقدام (Action Selection): عامل بر اساس مقادیر Q در وضعیت کنونی یک اقدام را انتخاب می‌کند. ممکن است اقدام با بالاترین مقدار Q را انتخاب کند (رویکرد طمع‌ورزانه (greedy approach)) یا مقداری تصادفی برای کاوش اضافه کند (رویکرد ائپسیلون-طمع‌ورزانه (epsilon-greedy approach)).

4.مشاهده و پاداش (Observation and Reward): عامل وضعیت بعدی را مشاهده کرده و بر اساس اقدام انجام‌شده، پاداشی دریافت می‌کند.

5.به‌روزرسانی مقدار Q (Q-Value Update): مقدار Q برای جفت اقدام-وضعیت قبلی با استفاده از معادله بلمن به‌روزرسانی می‌شود. این معادله پاداش فوری را با حداکثر پاداش آینده مورد انتظار تخفیف‌یافته از وضعیت بعدی ترکیب می‌کند.

6.تکرار (Iteration): مراحل ۲ تا ۵ تا زمانی که جدول Q همگرا شود، تکرار می‌شوند، به این معنی که مقادیر Q تثبیت می‌شوند و نشان‌دهنده این است که عامل سیاست بهینه را یاد گرفته است.

ملاحظات کلیدی

1.کاوش در برابر بهره‌برداری (Exploration vs. Exploitation): برقراری تعادل بین کاوش (تلاش برای چیزهای جدید) و بهره‌برداری (استفاده از آنچه که مؤثر است) برای یادگیری مؤثر بسیار مهم است.

2.عامل تخفیف (Discount Factor): این عامل اهمیت جوایز آینده را کنترل می‌کند. یک ضریب تخفیف بالاتر بر روی دستاوردهای بلندمدت تأکید می‌کند.

3.نرخ یادگیری (Learning Rate): این عامل میزان سرعت به‌روزرسانی مقادیر Q را تعیین می‌کند. یک نرخ یادگیری بالاتر به یادگیری سریع‌تر ولی احتمالاً کمتر پایدار منجر می‌شود.

مزایای Q-Learning

1.نتایج بلندمدت، که دستیابی به آن‌ها بسیار چالش‌برانگیز است، به بهترین شکل ممکن با این استراتژی تحقق می‌یابند.

2.این الگوی یادگیری به طرز نزدیکی شبیه به نحوه یادگیری انسان‌ها است؛ بنابراین، تقریباً ایده‌آل به شمار می‌آید.

3.مدل می‌تواند اشتباهات انجام‌شده در حین آموزش را اصلاح کند.

4.پس از اینکه یک مدل اشتباهی را اصلاح کرد، احتمال تکرار آن اشتباه به‌طور قابل توجهی کاهش می‌یابد.

5.این مدل قادر است یک راه‌حل ایده‌آل برای یک مسئله خاص ارائه دهد.

معایب Q-Learning

1.معایب استفاده از نمونه‌های واقعی را باید در نظر گرفت. به‌عنوان مثال، در زمینه یادگیری ربات‌ها، سخت‌افزار این ربات‌ها معمولاً بسیار گران، مستعد خرابی و نیازمند نگهداری دقیق است. هزینه تعمیر یک سیستم رباتیکی نیز بالا است.

2.به‌جای کنار گذاشتن کامل یادگیری تقویتی، می‌توان آن را با سایر تکنیک‌ها ترکیب کرد تا بسیاری از مشکلات آن کاهش یابد. یکی از ترکیب‌های رایج، ادغام یادگیری عمیق با یادگیری تقویتی است.

محدودیت‌های Q-Learning

1.فضاهای وضعیت و اقدام محدود(Finite State and Action Spaces):

Q-Learning نیاز به مجموعه‌ای محدود و گسسته از وضعیت‌ها و اقدام‌ها دارد. این به این دلیل است که بر اساس نگهداری یک جدول (جدول Q) عمل می‌کند که در آن سطرها نمایانگر وضعیت‌ها و ستون‌ها نمایانگر اقدام‌ها هستند. در محیط‌هایی که وضعیت‌ها یا اقدام‌ها بی‌نهایت یا بسیار بزرگ هستند، جدول Q به طرز غیرقابل مدیریتی بزرگ می‌شود یا مدیریت آن غیرممکن می‌گردد.

2.مشکلات مقیاس‌پذیری (Scaling Issues):

با افزایش اندازه فضاهای وضعیت و اقدام، حافظه مورد نیاز برای ذخیره جدول Q و منابع محاسباتی لازم برای به‌روزرسانی آن به‌طور نمایی افزایش می‌یابد. این موضوع باعث می‌شود Q-Learning برای مسائل پیچیده مانند رباتیک در دنیای واقعی کمتر قابل ‌اجرا باشد، جایی که فضای وضعیت می‌تواند شامل یک پیوستگی از مقادیر ممکن باشد.

3.سرعت همگرایی (Convergence Speed):

Q-Learning می‌تواند در همگرایی به سیاست بهینه به‌خصوص در محیط‌های بزرگ یا پیچیده کند باشد. این الگوریتم نیاز دارد تا تمام جفت‌های وضعیت-اقدام را به اندازه کافی بازدید کند تا بتواند مقادیر Q را به‌طور دقیق تخمین بزند، که این کار ممکن است زمان بسیار طولانی ببرد.

4.عدم تعمیم پذیری (Lack of Generalization):

از آنجایی که Q-Learning برای هر جفت وضعیت-اقدام خاص یک ارزش یاد می‌گیرد، نمی‌تواند در وضعیت‌های مشابه تعمیم یابد. این در تضاد با روش‌هایی است که مقادیر Q را تقریب می‌زنند و می‌توانند ارزش وضعیت‌های نادیده را بر اساس شباهت به وضعیت‌های قبلاً مشاهده‌شده استنباط کنند.

5.نیاز به کاوش (Requirement for Exploration):

Q-Learning نیاز به برقراری تعادل دقیق بین کاوش اقدام‌های جدید و بهره‌برداری از اقدام‌های شناخته‌شده برای حداکثر کردن جوایز دارد. پیدا کردن استراتژی مناسب کاوش (مانند  ε-greedy) حیاتی است و می‌تواند چالش‌برانگیز باشد، به‌ویژه در محیط‌هایی که برخی از اقدام‌ها می‌توانند به عواقب منفی قابل‌توجهی منجر شوند.

6.وابستگی به تمامی پاداش‌ها (Dependency on All Rewards):

عملکرد Q-Learning به شدت به ساختار پاداش‌ها وابسته است. اگر پاداش‌ها نادر یا گمراه‌کننده باشند، این الگوریتم ممکن است نتواند سیاست‌های مفیدی را یاد بگیرد.

7.مشاهده جزئی (Partial Observability):

Q-Learning فرض می‌کند که عامل دارای مشاهده کامل از وضعیت محیط است. در بسیاری از سناریوهای دنیای واقعی، عامل‌ها فقط مشاهده جزئی دارند که می‌تواند منجر به یادگیری و تصمیم‌گیری غیر بهینه شود.

به دلیل این محدودیت‌ها، پژوهشگران معمولاً به روش‌های دیگری مانند شبکه‌های Q عمیق (DQN) روی می‌آورند که از شبکه‌های عصبی برای تقریب مقادیر Q استفاده می‌کنند و می‌توانند با فضاهای وضعیت پیوسته و بزرگ مقابله کنند، یا انواع دیگری از الگوریتم‌های یادگیری که قادر به مدیریت مشاهده جزئی و پاداش‌های نادر هستند.

کاربردهای Q-Learning

کاربردهای Q-Learning، یک الگوریتم یادگیری تقویتی، در زمینه‌های مختلفی وجود دارد. در اینجا چند مورد قابل توجه آورده شده است:

1.بازی‌های آتاری (Atari Games): بازی‌های کلاسیک آتاری ۲۶۰۰ اکنون با استفاده از Q-learning قابل بازی هستند. در بازی‌هایی مانند Space Invaders و Breakout، شبکه‌های عمیق Q (DQN)، که نسخه‌ای از Q-learning است و از شبکه‌های عصبی عمیق استفاده می‌کند، عملکردی فراتر از انسان را نشان داده است.

1.کنترل ربات (Robot Control): Q-learning در رباتیک برای انجام وظایفی مانند ناوبری و کنترل ربات‌ها استفاده می‌شود. با استفاده از الگوریتم‌های Q-learning، ربات‌ها می‌توانند یاد بگیرند که چگونه در محیط‌ها حرکت کنند، از موانع دوری کنند و حرکات خود را بهینه‌سازی کنند.

2.مدیریت ترافیک (Traffic Management): سیستم‌های مدیریت ترافیک خودروهای خودران از Q-learning استفاده می‌کنند. این سیستم با بهینه‌سازی برنامه‌ریزی مسیر و زمان‌بندی چراغ‌های ترافیکی، موجب کاهش ترافیک و بهبود جریان کلی ترافیک می‌شود.

3.معامله‌گری الگوریتمی (Algorithmic Trading): استفاده از Q-learning برای اتخاذ تصمیمات معاملاتی در زمینه معامله‌گری الگوریتمی مورد بررسی قرار گرفته است. این روش به عوامل خودکار این امکان را می‌دهد که بهترین استراتژی‌ها را از داده‌های گذشته بازار یاد بگیرند و به شرایط متغیر بازار سازگار شوند.

4.برنامه‌های درمانی شخصی‌سازی‌شده (Personalized Treatment Plans): در حوزه پزشکی، از Q-learning برای ایجاد برنامه‌های درمانی منحصر به فرد استفاده می‌شود. با استفاده از داده‌های بیماران، عوامل می‌توانند مداخلات شخصی‌سازی‌شده‌ای را پیشنهاد دهند که پاسخ‌های فردی به درمان‌های مختلف را در نظر بگیرند.

Applications_Q-Learning
تصویر1-کاربردهای الگوریتم Q-Learning

ترتیبی که هوشینو برای خواندن مطالب یادگیری تقویتی به شما پیشنهاد می‌کند:

 

1.یادگیری تقویتی بخش اول

2.یادگیری تقویتی بخش دوم

3.یادگیری تقویتی بخش سوم

4.زنجیره مارکوف بخش اول

5.زنجیره مارکوف بخش دوم

6.زنجیره مارکوف بخش سوم

7.زنجیره مارکوف بخش چهارم

8.الگوریتم Q-Learning بخش اول

9.الگوریتم Q-Learning بخش دوم

10.الگوریتم Q-Learning بخش سوم

11.الگوریتم SARSA-بخش اول

12.الگوریتم SARSA-بخش دوم

13. تفاوت بین Q-Learning و SARSA

الگوریتم Q-Learning(بخش اول)
مقدمه

الگوریتم Q-Learning یکی از شناخته‌شده‌ترین و ساده‌ترین الگوریتم‌ها برای حل مسائلی است که با فرآیندهای تصمیم‌گیری مارکوف (MDP) مدل‌سازی می‌شوند. این الگوریتم که در دسته‌ی روش‌های یادگیری تقویتی (Reinforcement Learning) قرار دارد، به عامل‌ها (Agents) کمک می‌کند تا یاد بگیرند چگونه در محیط عمل‌های بهینه‌ای را انجام دهند که در نهایت منجر به بیشترین پاداش ممکن دست یابند.

Q-Learning چیست؟

Q-Learning یک الگوریتم یادگیری تقویتی بدون مدل است که به عامل (Agent) امکان می‌دهد تا از طریق به‌روزرسانی مکرر مقادیر Q، سیاست انتخاب عمل بهینه را یاد بگیرد. مقادیر Q، نمایانگر پاداش‌های مورد انتظار برای اقدامات مختلف در وضعیت‌های خاص هستند. عامل با تمرکز بر یادگیری ارزش هر عمل، بدون نیاز به مدل دقیق از محیط، سعی می‌کند به مقادیر بهینه‌ی Q دست یابد. در این روش، عامل با آزمون و خطا، از جمله کاوش (Exploration) برای شناخت بهتر محیط، گزینه‌های مختلف را بررسی می‌کند. کاوش به عامل این امکان را می‌دهد که با امتحان کردن اقدامات مختلف، اطلاعات بیشتری از محیط به دست آورد و تصمیم‌گیری‌های بهتری داشته باشد.

Labyrinth_Q-Learning
تصویر1-هزارتو

 

 

تصور کنید رباتی در یک هزارتو در حال حرکت است. Q-Learning به ربات این امکان را می‌دهد که هزارتو را کاوش کند، جوایز (مانند رسیدن به خروجی) را کشف کند و بیاموزد که کدام اقدامات (مثل چرخش به چپ یا راست) در مکان‌های مختلف هزارتو به آن جوایز منجر می‌شوند.

 

 

 

این الگوریتم زیرمجموعه‌ای از تکنیک‌های یادگیری تفاوت زمانی است، که در آن عامل با مشاهده نتایج، تعامل با محیط و دریافت بازخورد به شکل پاداش، اطلاعات جدید کسب می‌کند.

تفاوت الگوریتم‌های بدون مدل (Model-Free) و با مدل (Model-Based)

در یادگیری تقویتی، الگوریتم بدون مدل به نوعی از الگوریتم‌ها گفته می‌شود که نیازی به دانستن جزئیات ساختار محیط ندارد. در این الگوریتم‌ها، عامل تنها با تجربه و تعامل با محیط یاد می‌گیرد که در هر حالت بهترین اقدام چیست Q-Learning .نمونه‌ای از این الگوریتم‌هاست؛ در این روش، عامل به محاسبه‌ی مقداری به نام Q-Value می‌پردازد که نشان‌دهنده‌ی ارزش هر اقدام در وضعیت‌های مختلف است، بدون آنکه نیازی به دانستن ساختار محیط داشته باشد. عامل تنها نیاز دارد بداند که در ازای هر اقدام چه پاداشی دریافت می‌کند.

در مقابل، الگوریتم‌های با مدل مانند الگوریتم‌های برنامه‌ریزی پویا به اطلاعات کاملی از محیط نیاز دارند (مثلاً احتمال انتقال بین حالت‌ها) تا بتوانند نتایج اقدامات را پیش‌بینی و از این اطلاعات در تصمیم‌گیری استفاده کنند.

برای مثال، اگر بخواهید برای رباتی که در آزمایشگاهی حرکت می‌کند، الگوریتمی طراحی کنید:

الگوریتم بدون مدل(Q-Learning): به ربات اجازه می‌دهید با حرکت در آزمایشگاه یاد بگیرد که در هر نقطه و وضعیت (مانند کنار میز یا نزدیک دیوار)، بهترین اقدام چیست تا به هدف (مثلاً میز آزمایش) برسد. ربات در هر نقطه پاداش یا جریمه‌ای دریافت می‌کند و با تکرار، یاد می‌گیرد که کدام اقدامات او را سریع‌تر به هدف می‌رسانند.

الگوریتم با مدل: در این حالت، از پیش به ربات اطلاعات کامل محیط را می‌دهید، مانند «اگر از نقطه‌ی A به سمت B حرکت کنی، با ۹۰٪ احتمال به نقطه C خواهی رسید». ربات از این اطلاعات برای پیش‌بینی بهترین مسیر استفاده کرده و تصمیمات خود را بر اساس این پیش‌بینی‌ها بهینه می‌کند.

مولفه‌های کلیدی Q-Learning

1.Q-Values or Action-Values

مقادیر Q برای حالت‌ها و اقدامات تعریف می‌شوند. به طوری که Q(s,a) نشان‌دهنده‌ی تخمینی از میزان مطلوبیت انجام اقدام a در حالت s است. این مقدار، به‌طور تدریجی با استفاده از قانون به‌روزرسانی تفاوت زمانی (TD-Update) محاسبه می‌شود.

2.پاداش‌ها و قسمت‌ها (Rewards and Episodes)

یک عامل در طول عمر خود از یک حالت شروع (start state) آغاز می‌کند و با انتخاب اقدامات مختلف و تعامل با محیط، چندین انتقال از حالت فعلی به حالت بعدی را تجربه می‌کند. در هر مرحله، عامل از یک حالت عملی را انتخاب می‌کند، پاداشی از محیط دریافت می‌کند و سپس به حالت دیگری منتقل می‌شود. اگر در هر نقطه از زمان عامل به یکی از حالت‌های پایانی (terminating states) برسد، به این معناست که دیگر امکان انجام انتقال‌های بیشتر وجود ندارد و این وضعیت به عنوان پایان یک قسمت (episode) شناخته می‌شود.

3.تفاوت زمانی (Temporal Difference یا TD-Update)

قانون تفاوت زمانی یا TD-Update به صورت زیر نمایش داده می‌شود:

 

Q Function

این قانون به‌روزرسانی برای تخمین مقدار Q در هر مرحله زمانی تعامل عامل با محیط اعمال می‌شود. عبارات به‌کار رفته در این قانون به شرح زیر توضیح داده می‌شوند:

s: وضعیت فعلی عامل است.

a: عملکرد فعلی که بر اساس یک سیاست خاص انتخاب شده است.

s’: حالت بعدی که عامل به آن منتقل می‌شود.

a’: بهترین اقدام بعدی که باید با استفاده از تخمین فعلی مقدار Q انتخاب شود، به این معنی که اقدام با حداکثر مقدار Q در حالت بعدی انتخاب شود.

پاداش فوری (R): پاداشی است که عامل بلافاصله پس از انجام اقدام a در حالت s دریافت می‌کند. این پاداش به عنوان بازخوردی از محیط عمل می‌کند.

ضریب تخفیف (𝛾): این پارامتر اهمیت پاداش‌های آینده را نسبت به پاداش‌های فوری مشخص می‌کند که معمولا بین 0 و 1 است. مقدار γ نزدیک به 1 به این معناست که عامل به پاداش‌های آینده بیشتر اهمیت می‌دهد.

نرخ یادگیری  (α): این پارامتر تعیین‌کننده‌ی سرعت به‌روزرسانی مقادیر Q است و مقدار آن بین 0 و 1 قرار دارد. مقادیر بالاتر α به معنای یادگیری سریع‌تر هستند، اما ممکن است موجب ناپایداری مقادیر Q شوند.

Q(s,a): مقدار Q برای حالت s و اقدام a است که نشان‌دهنده‌ی تخمینی از مطلوبیت انجام اقدام a در حالت s می‌باشد.

maxQ  : این عبارت نشان‌دهنده‌ی بیشترین مقدار Q برای تمام اقدامات ممکن a’ در حالت جدید s’ است و به عامل کمک می‌کند تا بهترین گزینه را برای اقدامات آینده شناسایی کند.

این قانون به‌روزرسانی با مقایسه مقدار فعلی Q(s,a) با ترکیب پاداش فوری و بهترین مقدار Q در حالت جدید، به تدریج مقادیر Q را به سمت مقادیر بهینه هدایت می‌کند.

4.انتخاب مسیر عمل با استفاده از سیاست ϵ-greedy (Selecting the Course of Action with ϵ-greedy policy)

یک روش ساده برای انتخاب اقدام بر اساس تخمین‌های کنونی مقدار Q، سیاست ϵ-greedy است. این سیاست به این صورت عمل می‌کند:

اقدام با مقدار Q برتر (بهره‌برداری یا Exploitation) (Superior Q-Value Action (Exploitation)):

1.استراتژی ϵ-greedy: عامل تصمیم‌گیری خود را بر اساس این استراتژی انجام می‌دهد که در بیشتر موارد به انتخاب اقدامات می‌پردازد.

2.انتخاب اقدام با بالاترین مقدار Q: در حالتی که عامل بهره‌برداری می‌کند، او عملی را انتخاب می‌کند که در حال حاضر بالاترین مقدار Q را دارد.

3.بهینه‌سازی بر اساس درک کنونی: در این حالت بهره‌برداری، عامل مسیری را انتخاب می‌کند که با توجه به درک کنونی‌اش، آن را بهینه می‌داند.

کاوش از طریق اقدام تصادفی (Exploration through Random Action):

1.احتمال ϵ: با احتمال ϵ ، عامل به‌جای انتخاب مسیری که بالاترین مقدار Q را دارد، تصمیم‌گیری می‌کند.

2.انتخاب تصادفی اقدام: در این حالت، عامل هر اقدامی را به‌صورت تصادفی انتخاب می‌کند، صرف‌نظر از مقادیر Q مربوط به آن اقدامات.

3.کاوش برای یادگیری: این انتخاب تصادفی به عامل این امکان را می‌دهد که درباره مزایای احتمالی اقدامات جدید یاد بگیرد و به نوعی کاوش کند.

Q-Learning چگونه کار می‌کند؟

مدل‌های Q-Learning  در یک فرایند تکراری شرکت می‌کنند که در آن اجزای مختلف به همکاری برای آموزش مدل می‌پردازند. این فرایند تکراری شامل کاوش عامل در محیط و به‌روزرسانی مداوم مدل بر اساس این کاوش است.

مولفه‌های کلیدی Q-Learning عبارتند از:

1.عامل (Agents): موجودیت‌هایی که در یک محیط فعالیت می‌کنند، تصمیم‌گیری می‌کنند و اقداماتی را انجام می‌دهند.

2.وضعیت (States): متغیرهایی که موقعیت کنونی یک عامل را در محیط شناسایی می‌کنند.

3.اقدام (Actions): عملیاتی که عامل در حالت‌های خاص انجام می‌دهد.

4.پاداش (Rewards): پاسخ‌های مثبت یا منفی که بر اساس اقدامات عامل به او ارائه می‌شود.(بازخوردهایی که بعد از انجام یک عمل دریافت می‌کنیم.)

5.قسمت (Episodes): مواردی که در آن عامل فعالیت‌های خود را به پایان می‌رساند و پایان یک قسمت را مشخص می‌کند.

6.Q-Value: معیارهایی که برای ارزیابی اقدامات در حالت‌های خاص استفاده می‌شوند.

روش‌های تعیین ارزش Q  (Q-Values)

دو روش برای تعیین مقادیر Q وجود دارد:

1.تفاوت زمانی (Temporal Difference): محاسبه شده با مقایسه مقادیر حالت و اقدام کنونی با مقادیر قبلی.

2.معادله بلمن (Bellman’s Equation):

  • الگوریتم Q-Learning بر پایه‌ی معادله‌ی بلمن است که ابتدا توسط ریچارد بلمن برای محاسبه‌ی ارزش یک حالت خاص در فرآیندهای تصمیم‌گیری مارکوف (MDP) معرفی شد. این معادله بیان می‌کند که ارزش یک وضعیت، برابر است با مجموع پاداش فوری آن و ارزش تخفیف‌یافته‌ی بهترین موقعیتی که می‌توان از آن به دست آورد.
  • Q-Learning این مفهوم را گسترش داده و به ارزیابی اقدام‌های ممکن در هر وضعیت می‌پردازد، با این هدف که بهترین اقدام را برای هر وضعیت شناسایی و ارزش آن را محاسبه کند. به این ترتیب، Q-Learning به دنبال پاسخ به این سؤال است: “در هر وضعیت، کدام اقدام بیشترین ارزش را دارد و به تصمیم‌گیری بهینه منجر می‌شود؟”

فرمول معادله بلمن:

Bellman equation

توضیح بخش‌ها:

Q(s,a): مقدار Q  ارزش تخمینی ناشی از انجام اقدام a در وضعیت s

R(s,a): پاداش فوری دریافتی به خاطر انجام اقدام a  در وضعیت s.

γ: عامل تخفیف است که اهمیت پاداش‌های آینده را نشان می‌دهد. که معمولا بین 0 و 1 است.

maxqa : حداکثر مقدار Q برای حالت بعدی s′ و تمام اقدامات ممکن است.


ترتیبی که هوشینو برای خواندن مطالب یادگیری تقویتی به شما پیشنهاد می‌کند:

 

1.یادگیری تقویتی بخش اول

2.یادگیری تقویتی بخش دوم

3.یادگیری تقویتی بخش سوم

4.زنجیره مارکوف بخش اول

5.زنجیره مارکوف بخش دوم

6.زنجیره مارکوف بخش سوم

7.زنجیره مارکوف بخش چهارم

8.الگوریتم Q-Learning بخش اول

9.الگوریتم Q-Learning بخش دوم

10.الگوریتم Q-Learning بخش سوم

11.الگوریتم SARSA-بخش اول

12.الگوریتم SARSA-بخش دوم

13. تفاوت بین Q-Learning و SARSA

زنجیره مارکوف بخش چهارم
کاربردهای زنجیره مارکوف در الگوریتم‌ها

1.الگوریتم Viterbi

2.الگوریتم Forward-Backward

3.الگوریتم PageRank

4.الگوریتم Monte Carlo

5.الگوریتم Q-learning

6.الگوریتم POMDP (Partially Observable Markov Decision Process)

7.الگوریتم Hidden Markov Model (HMM)

8.الگوریتم Reinforcement Learning

9.الگوریتم Dynamic Programming

1.الگوریتم Viterbi

کاربرد زنجیره مارکوف:

الگوریتم Viterbi به‌ویژه در مدل‌های مارکوف پنهان (HMM) استفاده می‌شود تا بهترین دنباله‌ای از حالات پنهان را پیدا کند که احتمال مشاهده یک دنباله خاص از نشانه‌ها را حداکثر می‌کند. به عبارت دیگر، این الگوریتم تلاش می‌کند بفهمد چه اتفاقاتی در پس‌زمینه (حالات پنهان) باعث ایجاد مشاهدات (صداها، کلمات و غیره) شده است.

مثال: فرض کنید در حال تحلیل گفتار یک فرد هستید. هر بار که فرد صحبت می‌کند، ممکن است او در یکی از چند حالت قرار داشته باشد: خواب، کار یا تفریح. با استفاده از الگوریتم Viterbi، می‌توانید به بهترین نحو تعیین کنید که فرد در هر لحظه کدام وضعیت را تجربه می‌کند، بر اساس نشانه‌هایی که از او دریافت می‌کنید (مانند اینکه او چه کلماتی می‌گوید).

2.الگوریتم Forward-Backward

کاربرد زنجیره مارکوف:

این الگوریتم به‌منظور محاسبه احتمال یک دنباله از نشانه‌ها در یک مدل مارکوف پنهان (HMM) استفاده می‌شود. با استفاده از این الگوریتم، می‌توانیم بفهمیم که چگونه یک مدل به مشاهدات رسیده است و چه احتمالی برای هر حالت وجود دارد.

مثال: فرض کنید شما در حال تشخیص احساسات یک شخص هستید. با گوش دادن به صداهای او (نشانه‌ها) و استفاده از Forward-Backward، می‌توانید محاسبه کنید که چه احساسی (شادی، غم و …) احتمال بیشتری دارد با توجه به نشانه‌های خاصی که شنیده‌اید.

3.الگوریتم PageRank گوگل:

کاربرد زنجیره مارکوف:

PageRank به‌طور خاص برای رتبه‌بندی صفحات وب بر اساس اهمیت آن‌ها استفاده می‌شود. این الگوریتم به عنوان یک زنجیره مارکوف مدل می‌کند که چگونه کاربران از یک صفحه به صفحه دیگر می‌روند. اگر یک صفحه وب به چندین صفحه دیگر لینک داده باشد، این صفحات دیگر نیز به آن صفحه اهمیت بیشتری می‌دهند.

Algorithm_PageRank_Google
تصویر1-الگوریتم PageRank گوگل

این تصویر الگوریتم PageRank گوگل را به‌صورت شبکه‌ای از گره‌ها و اتصالات نمایش می‌دهد که سایت‌ها و ارتباطات بین آن‌ها را از نظر اهمیت رتبه‌بندی نشان می‌دهد.

مثال: تصور کنید وب‌سایتی دارید که به چندین وب‌سایت دیگر لینک داده است. با استفاده از PageRank، می‌توانید بفهمید که آیا وب‌سایت شما به اندازه کافی مهم است یا خیر، بر اساس اینکه چه تعداد صفحه به آن لینک داده‌اند و این صفحات چقدر معتبر هستند.

4.الگوریتم Monte Carlo

کاربرد زنجیره مارکوف:

روش‌های Monte Carlo از زنجیره‌های مارکوف برای تولید نمونه‌های تصادفی از یک توزیع استفاده می‌کنند. این روش‌ها می‌توانند برای برآورد مقادیر مورد نیاز در مسائل پیچیده و در شرایط عدم قطعیت استفاده شوند.

مثال: فرض کنید می‌خواهید مساحت یک شکل پیچیده را محاسبه کنید. می‌توانید از زنجیره مارکوف برای تولید نقاط تصادفی در یک مستطیل حاوی آن شکل استفاده کنید و سپس با شمارش تعداد نقاطی که درون شکل قرار دارند، مساحت آن را برآورد کنید.

5.الگوریتم Q-learning

کاربرد زنجیره مارکوف:

Q-learning یک روش یادگیری تقویتی است که به ماشین‌ها یاد می‌دهد چگونه بهترین تصمیمات را در یک محیط مشخص بگیرند. این الگوریتم بر اساس فرایند تصمیم‌گیری مارکوف (MDP) کار می‌کند و به ماشین‌ها اجازه می‌دهد از تجربیاتشان بیاموزند.

مثال: فرض کنید یک ربات در حال یادگیری نحوه پیمایش در یک اتاق است. این ربات با استفاده از Q-learning یاد می‌گیرد که هر بار که حرکتی انجام می‌دهد، چه پاداشی دریافت می‌کند و می‌تواند بهترین راه را برای رسیدن به هدفش پیدا کند. به این ترتیب، ربات به تدریج بهتر و بهتر می‌شود.

6.الگوریتم POMDP (Partially Observable Markov Decision Process)

در فرایند تصمیم‌گیری مارکوف جزئی (POMDP)، عامل نمی‌تواند به طور کامل حالت سیستم را مشاهده کند. ؛ یعنی حالت‌ها به‌صورت کامل برای عامل قابل مشاهده نیستند. در این موارد از تصمیم‌گیری مارکوف جزئی استفاده می‌شود. این مدل پیچیده‌تر است و علاوه بر حالت‌ها، شامل یک تابع باور (belief) نیز می‌شود که احتمال حضور در هر حالت را با توجه به مشاهدات عامل تخمین می‌زند.

فرض کنید شما در یک هزارتوی تاریک هستید و نمی‌توانید به‌طور دقیق ببینید در کدام اتاق هستید، اما از طریق نشانه‌های محیطی (مثل صدا یا دما) به‌طور تقریبی می‌توانید بفهمید در کدام اتاق هستید. اینجا یک “تابع باور” وجود دارد که احتمالات حضور شما در هر اتاق را به‌روز می‌کند.

کاربرد زنجیره مارکوف:

فرایند تصمیم‌گیری مارکوف جزئی یک مدل تعمیم‌یافته از فرایند تصمیمگیری مارکوف است که در آن اطلاعات برخی از حالت‌ها پنهان است. این الگوریتم به‌منظور تصمیم‌گیری در شرایط عدم قطعیت و در زمانی که نمی‌توانیم وضعیت دقیق محیط را مشاهده کنیم، استفاده می‌شود.

مثال: تصور کنید که یک ربات در یک اتاق تاریک حرکت می‌کند و نمی‌تواند ببیند. فرایند تصمیم‌گیری مارکوف جزئی به ربات کمک می‌کند با استفاده از اطلاعات محدود و گذشته خود، تصمیمات بهتری بگیرد و هدفش را پیدا کند.

7.الگوریتم Hidden Markov Model (HMM)

کاربرد زنجیره مارکوف:

مدل مارکوف پنهان یکی از ابزارهای قدرتمند برای تجزیه و تحلیل دنباله‌های زمانی است. این الگوریتم به‌طور خاص برای پیش‌بینی و تشخیص وضعیت‌های پنهان بر اساس نشانه‌های مشهود استفاده می‌شود.

مثال: در تشخیص گفتار، مدل مارکوف پنهان می‌تواند به ما کمک کند تا بفهمیم فرد در حال بیان چه کلماتی است، با توجه به صداهایی که ضبط کرده‌ایم. این مدل فرض می‌کند که وضعیت فعلی (کلمه) تنها به وضعیت قبلی وابسته است و از این رو می‌تواند دقت بالایی در تشخیص گفتار داشته باشد.

8.الگوریتم Reinforcement Learning

کاربرد زنجیره مارکوف:

یادگیری تقویتی بر اساس فرایند تصمیم‌گیری مارکوف و زنجیره‌های مارکوف کار می‌کند و به ماشین‌ها این امکان را می‌دهد تا با یادگیری از تجربیات خود، اقداماتی انجام دهند که بیشترین پاداش را برای آن‌ها به ارمغان بیاورد.

مثال: تصور کنید که یک بازیکن در یک بازی ویدئویی قرار دارد. او باید با یادگیری از اقداماتی که در بازی انجام می‌دهد، بهترین حرکات را پیدا کند. یادگیری تقویتی به بازیکن کمک می‌کند تا با یادگیری از تجربیاتش، نقاط قوت و ضعف خود را شناسایی کند و به تدریج بهتر شود.

9.الگوریتم Dynamic Programming

کاربرد زنجیره مارکوف:

از روش‌های برنامه‌ریزی پویا برای حل مسائل بهینه‌سازی و فرایند تصمیم گیری مارکوف استفاده می‌شود. این الگوریتم‌ها با شکستن یک مشکل بزرگ به زیرمسائل کوچکتر، کارایی بیشتری را به ارمغان می‌آورند.

مثال: فرض کنید می‌خواهید هزینه کمترین مسیر را از یک نقطه به نقطه دیگر در یک نقشه محاسبه کنید. با استفاده از برنامه‌ریزی پویا، می‌توانید از زنجیره مارکوف برای محاسبه هزینه هر مسیر استفاده کنید و بهترین مسیر را پیدا کنید.

زمان‌بندی و  فرایند تصمیم گیری مارکوف با زمان گسسته یا پیوسته

در بسیاری از فرایند تصمیم گیری مارکوف زمان به‌صورت گسسته در نظر گرفته می‌شود؛ یعنی در هر لحظه تنها یک عمل انجام می‌شود و سپس سیستم به حالت بعدی منتقل می‌شود. اما در برخی مسائل، زمان به صورت پیوسته است و سیستم می‌تواند در هر لحظه از زمان عمل کند. این مدل‌ها پیچیده‌تر هستند و به فرایند تصمیم گیری مارکوف با زمان پیوسته معروف‌اند.

در MDPهای محدود، علاوه بر تلاش برای بهینه‌سازی پاداش، باید به محدودیت‌هایی مثل منابع انرژی یا زمان نیز توجه کنید.

مثال: فرض کنید یک ربات دارید که باید وظایف مختلفی را انجام دهد، اما تنها باتری محدودی دارد. در اینجا علاوه بر اینکه می‌خواهید وظایف را به بهترین نحو انجام دهید، باید مطمئن شوید که ربات قبل از خالی شدن باتری به اتمام کارهایش می‌رسد.

چگونه به مرحله همگرا شدن می‌رسیم ؟

در زنجیره‌های مارکوف، هدف شما این است که پس از طی یک تعداد معینی از مراحل، توزیع احتمالات حالت‌ها به یک توزیع ثابت یا پایدار (که به آن توزیع پایدار یا توزیع ایستا می‌گویند) همگرا شود. این توزیع پایدار، زمانی به دست می‌آید که زنجیره به حالت تعادل برسد و دیگر تغییرات قابل توجهی در توزیع احتمالات حالت‌ها رخ ندهد.

مراحل رسیدن به توزیع پایدار:

1.نوشتن ماتریس انتقال احتمالات :

 

Climate transfer matrix

ابتدا باید ماتریس انتقال احتمالات را تعریف کنیم. فرض کنید که دو حالت داریم:

  • حالت آفتابی (S)
  • حالت ابری (C)
  • ماتریس انتقال احتمالات P به صورت روبرو است :
  • SSP یعنی احتمال اینکه فردا آفتابی باشد ، اگر امروز آفتابی باشد.
  • SCP یعنی احتمال اینکه فردا ابری باشد ، اگر امروز آفتابی باشد.
  • CSP یعنی احتمال اینکه فردا آفتابی باشد ، اگر امروز ابری باشد.
  • CCP یعنی احتمال اینکه ابری آفتابی باشد ، اگر امروز ابری باشد.

2.یافتن توزیع پایدار :

  • توزیع پایدار، توزیعی است که با گذر زمان تغییر نمی‌کند. برای یافتن این توزیع، باید برداری را پیدا کنیم که وقتی با ماتریس انتقال P ضرب می‌شود، خودش را تولید کند:
  • این معادله به این معناست که توزیع جدید  همانند توزیع قبلی است و هیچ تغییر معنی‌داری در توزیع ایجاد نمی‌شود.

3.نوشتن معادلات :

  • از معادله فوق، معادلات زیر به دست می‌آید:

 

 

The first equation

4.شرط نرمالسازی :

  • چون مجموع احتمالات باید برابر با 1 باشد، یک شرط نرمال‌سازی داریم:

normalization condition

5.حل دستگاه معادلات :

  • حالا این معادلات را حل می‌کنیم تا مقادیر و  (توزیع پایدار) را به دست آوریم.

مثال عملی :

فرض کنید که ماتریس انتقال به شکل زیر باشد:

transition matrix

1.نوشتن معادلات توزیع پایدار :

  • معادلات زیر را داریم:

Stable distribution equations

2.حل معادله اول :

  • از معادله اول می‌نویسیم:

Solving the first equation

  • این را حل می‌کنیم :

Solving the equation

3.استفاده از شرط نرمالسازی :

  • با استفاده از شرط نرمال‌سازی:

 

Using the normalization condition

نتیجه‌گیری

توزیع پایدار برای این زنجیره مارکوف به صورت زیر است:

0.75 =   (احتمال آفتابی)

0.25 =  (احتمال ابری)


ترتیبی که هوشینو برای خواندن مطالب یادگیری تقویتی به شما پیشنهاد می‌کند:

 

1.یادگیری تقویتی بخش اول

2.یادگیری تقویتی بخش دوم

3.یادگیری تقویتی بخش سوم

4.زنجیره مارکوف بخش اول

5.زنجیره مارکوف بخش دوم

6.زنجیره مارکوف بخش سوم

7.زنجیره مارکوف بخش چهارم

8.الگوریتم Q-Learning بخش اول

9.الگوریتم Q-Learning بخش دوم

10.الگوریتم Q-Learning بخش سوم

11.الگوریتم SARSA-بخش اول

12.الگوریتم SARSA-بخش دوم

13. تفاوت بین Q-Learning و SARSA