بایگانی‌های بدون مدل

مقدمه

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

Q-Learning چیست؟

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

تصور کنید رباتی در یک هزارتو در حال حرکت است. 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 در هر مرحله زمانی تعامل عامل با محیط اعمال می‌شود. عبارات به‌کار رفته در این قانون به شرح زیر توضیح داده می‌شوند:

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

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

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

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

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

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

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

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

: این عبارت نشان‌دهنده‌ی بیشترین مقدار 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