تفاوت بین Q-Learning و SARSAمروری بر Q-Learning

Q-learning یک الگوریتم یادگیری تقویتی خارج از سیاست (off-policy) است که ارزش بهترین عمل ممکن را مستقل از سیاستی که دنبال می‌شود، یاد می‌گیرد.

هدف این الگوریتم یادگیری تابع ارزش عمل بهینه Q∗(s,a) است که بیشترین پاداش مورد انتظار آینده را برای انجام عمل a  در حالت s می‌دهد. قانون به‌روزرسانی برای Q-learning به این صورت است:

مروری بر SARSA

در مقابل، SARSA یک الگوریتم یادگیری تقویتی روی سیاست (on-policy) است. این الگوریتم نیز یک تابع ارزش عمل را یاد می‌گیرد، اما تخمین‌های خود را براساس عملی که واقعاً توسط سیاست فعلی انجام شده، به‌روزرسانی می‌کند. قانون به‌روزرسانی برای SARSA به این صورت است:

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

تفاوت‌های کلیدی بین Q-Learning و SARSA

1.اکتشاف در مقابل بهره‌برداری (Exploration vs. Exploitation)

• Q-Learning: به‌عنوان یک روش خارج از سیاست (off-policy) است، Q-learning مقدارهای Q خود را با استفاده از بیشترین پاداش ممکن آینده به‌روزرسانی می‌کند، بدون توجه به اینکه کدام عمل انجام شده است. این ویژگی می‌تواند به جستجوی تهاجمی‌تر محیط منجر شود.

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

• SARSA: به‌عنوان یک روش روی سیاست (on-policy) است، SARSA مقدارهای Q خود را براساس اعمالی که واقعاً توسط سیاست انجام شده‌اند، به‌روزرسانی می‌کند. این ویژگی معمولاً به یک رویکرد محتاطانه‌تر منجر می‌شود که به شکل محافظه‌کارانه‌تری بین اکتشاف (exploration) و بهره‌برداری (exploitation) تعادل برقرار می‌کند.

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

2.به‌روزرسانی قوانین (Update Rules)

• Q-Learning: از عملگر بیشینه (max) برای به‌روزرسانی مقادیر Q استفاده می‌کند و روی بهترین عمل ممکن تمرکز دارد.

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

• SARSA: از عملی که توسط سیاست فعلی انتخاب شده است استفاده می‌کند، که باعث می‌شود فرآیند یادگیری بیشتر به رفتار سیاست وابسته باشد.

این بدان معناست که SARSA مقادیر Q را براساس عمل واقعی انجام‌شده طبق سیاست فعلی به‌روزرسانی می‌کند، و به همین دلیل، یادگیری آن به شدت به نحوه رفتار سیاست در محیط بستگی دارد. این وابستگی به سیاست باعث می‌شود SARSA به‌طور طبیعی تعادلی میان اکتشاف و بهره‌برداری برقرار کند، و در نتیجه رفتار محتاطانه‌تری را نسبت به Q-learning ارائه دهد.

3.یادگیری Off-Policy در مقابل On-Policy (On-policy vs. Off-policy Learning)

• Q-Leaning: یک روش خارج از سیاست (off-policy) است، به این معنا که ارزش سیاست بهینه را به‌طور مستقل از اعمالی که عامل انجام می‌دهد، یاد می‌گیرد.

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

• SARSA: یک روش روی سیاست (on-policy) است، به این معنا که ارزش سیاستی را که عامل در حال دنبال کردن آن است، یاد می‌گیرد.

این یعنی SARSA به‌طور مستقیم با استفاده از سیاست فعلی عامل، مقدارهای Q را به‌روزرسانی می‌کند. در نتیجه، یادگیری SARSA به اعمالی که عامل طبق سیاست جاری خود انجام می‌دهد، وابسته است. این ویژگی باعث می‌شود SARSA ارزش‌های Q را براساس سیاست جاری به دست آورد و به‌طور طبیعی میان اکتشاف و بهره‌برداری تعادلی ایجاد کند.

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

ویژگی	Q-Leaning	SARSA
نوع سیاست (Policy Type)	خارج از سیاست ( Off-policy)	روی سیاست ( On-policy)
به‌روزرسانی قوانین (Update Rule)
رویکرد یادگیری ( Learning Approach)	ارزش سیاست بهینه را یاد می‌گیرد.	ارزش سیاست فعلی را یاد می‌گیرد.
ثبات ( Stability)	به‌خاطر به‌روزرسانی‌های خارج از سیاست، ممکن است کمتر پایدار باشد.	به‌خاطر به‌روزرسانی‌های درون‌سیاست، پایدارتر است.
سرعت همگرایی ( Convergence Speed)	معمولاً همگرایی سریع‌تری به سیاست بهینه دارد.	معمولاً همگرایی کندتری به سیاست بهینه دارد.
تاثیر اکتشاف ( Exploration Impact)	سیاست کاوش می‌تواند با سیاست یادگیری متفاوت باشد.	کاوش به‌طور مستقیم بر به‌روزرسانی‌های یادگیری تأثیر می‌گذارد.
انتخاب اقدام برای بروزرسانی ( Action Selection for Update)	به‌روزرسانی‌ها بر اساس حداکثر پاداش آینده انجام می‌شوند.	به‌روزرسانی‌ها بر اساس عملی که واقعاً انجام شده‌اند، صورت می‌گیرند.
کاربرد (Use Case Suitability)	مناسب برای محیط‌هایی که کارایی حیاتی است.	مناسب برای محیط‌هایی که ثبات حیاتی است.
سناریوهای نمونه ( Example Scenarios)	بازی‌سازی (Gaming)، رباتیک (robotics)، تجارت مالی (financial trading)	بهداشت و درمان (Healthcare)، مدیریت ترافیک تطبیقی (adaptive traffic management)، یادگیری شخصی‌سازی‌شده (personalized learning)
رسیدگی به اقدامات اکتشافی ( Handling of Exploratory Actions)	بیشتر کارآمد است اما ممکن است با تجربیات واقعی کمتر هم‌راستا باشد.	بیشتر محتاط و هم‌راستا با تجربیات واقعی است.
تمرکز الگوریتم ( Algorithm Focus)	بر روی یافتن بهترین اقدامات ممکن تمرکز دارد.	بر روی اقداماتی که در حال حاضر توسط عامل انجام می‌شود تمرکز دارد.
تحمل ریسک ( Risk Tolerance)	تحمل بالاتری برای ریسک و بی‌ثباتی دارد.	تحمل کمتری برای ریسک دارد و ایمنی را در اولویت قرار می‌دهد.

1.Q-Learning: کارایی حیاتی

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

کارایی حیاتی: در محیط‌هایی که کارایی (Performance) بالایی نیاز است، Q-Learning می‌تواند انتخاب‌های بهتری را انجام دهد زیرا از تجربیات گذشته‌اش برای بهبود تصمیمات آینده استفاده می‌کند. به عبارت دیگر، Q-Learning به عامل این امکان را می‌دهد که خود را سریعاً با تغییرات محیط سازگار کند و یادگیری سریعی داشته باشد.

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

2.SARSA: ثبات حیاتی

SARSA (State-Action-Reward-State-Action) نیز یک الگوریتم یادگیری تقویتی است، اما تفاوت آن با Q-Learning در این است که SARSA از سیاست فعلی خود برای به‌روزرسانی Q-Values استفاده می‌کند. این به این معنی است که SARSA یاد می‌گیرد که چطور به‌طور پیوسته با سیاست فعلی‌اش عمل کند.

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

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

بطور کلی Q-Learning برای محیط‌هایی که کارایی حیاتی است مناسب است زیرا به سرعت می‌تواند بهترین عمل‌ها را یاد بگیرد و بهینه‌سازی کند و SARSA برای محیط‌هایی که ثبات حیاتی است مناسب است زیرا از سیاست فعلی خود پیروی می‌کند و یادگیری تدریجی‌تری دارد که تغییرات را به حداقل می‌رساند.

نقاط قوت و ضعف (Strengths and Weaknesses)

Q-Learning

نقاط قوت (Strengths):

• معمولاً سریع‌تر به سیاست بهینه همگرا می‌شود.

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

• Q-learning در اکتشاف محیط بسیار تهاجمی‌تر است که می‌تواند در سناریوهای پیچیده مفید باشد.

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

نقاط ضعف (Weaknesses):

• Q-learning می‌تواند به دلیل اکتشاف تهاجمی، از نظر پایداری کمتر قابل اعتماد باشد.

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

• Q-learning ممکن است به سیاست‌های زیر بهینه همگرا شود اگر اکتشاف به درستی مدیریت نشود.

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

SARSA

نقاط قوت (Strengths):

• فرآیند یادگیری در SARSA به دلیل رویکرد روی سیاست (on-policy) پایدارتر است.

این ثبات به این دلیل است که SARSA مقادیر Q را براساس اعمال واقعی انجام‌شده طبق سیاست فعلی به‌روزرسانی می‌کند. به همین دلیل، یادگیری کمتر تحت تأثیر نوسانات ناشی از اکتشافات تهاجمی قرار می‌گیرد و معمولاً به تغییرات تدریجی‌تری در مقدارهای Q منجر می‌شود. این ویژگی به عامل کمک می‌کند تا به آرامی به یک سیاست بهینه نزدیک شود و در عین حال رفتار مطمئن‌تری را در محیط ارائه دهد.

• SARSA در مدیریت محیط‌هایی با سطوح بالای عدم قطعیت بهتر عمل می‌کند.

این به این دلیل است که SARSA به‌طور مستقیم به سیاست فعلی وابسته است و مقادیر Q را براساس اعمال واقعی انجام‌شده به‌روزرسانی می‌کند. این رویکرد به آن اجازه می‌دهد تا به‌تدریج و با دقت بیشتری یاد بگیرد و به نوسانات غیرمنتظره در پاداش‌ها و وضعیت‌ها پاسخ دهد. در محیط‌های نامشخص، این ویژگی به SARSA کمک می‌کند تا به‌طور مؤثری به تغییرات پاسخ دهد و به سیاست‌های بهینه‌ای دست یابد که متناسب با شرایط پیچیده و متغیر محیط باشد.

نقاط ضعف (Weaknesses):

• SARSA ممکن است به دلیل تعادل بین اکتشاف و بهره‌برداری، به آهستگی همگرا شود.

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

• SARSA ممکن است به اندازه Q-learning به‌طور کامل اکتشاف نکند و در نتیجه ممکن است سیاست‌های بهینه را از دست بدهد.

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

نتیجه گیری

در نتیجه، Q-learning و SARSA الگوریتم‌های بنیادی یادگیری تقویتی هستند که رویکردهای متفاوتی دارند: Q-learning یک روش خارج از سیاست (off-policy) است، زیرا به دنبال یافتن مقادیر بهینه برای جدول Q است که در آینده بیشترین بازده را به همراه داشته باشد. این ویژگی آن را برای محیط‌های پویا مانند بازی‌ها و رباتیک مناسب می‌سازد. از سوی دیگر، SARSA یک روش روی سیاست (on-policy) است، زیرا از عمل فعلی عامل یاد می‌گیرد و به همین دلیل از نظر ایمنی و ثبات بیشتر، به‌ویژه در حوزه‌های مراقبت‌های بهداشتی، کنترل ترافیک و مدیریت، بهتر عمل می‌کند.

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

سوالات متدوال

تفاوت اصلی در قانون به‌روزرسانی بین Q-learning و SARSA چیست؟

به‌روزرسانی مقدار Q در Q-learning بر اساس حداکثر پاداش ممکن در حالت بعدی انجام می‌شود، نه بر اساس پاداشی که در عمل انتخاب شده است (روش خارج از سیاست یا off-policy)  این ویژگی اهمیت دارد زیرا SARSA مقدار Q را با استفاده از عملی که واقعاً توسط عامل انجام شده است، به‌روزرسانی می‌کند (روش روی سیاست یا on-policy)

این تفاوت بنیادی باعث می‌شود که Q-learning بتواند به‌طور تهاجمی‌تری به دنبال بهترین سیاست‌ها باشد، در حالی که SARSA از رویکردی محتاطانه‌تر استفاده می‌کند که به اعمال واقعی و پاداش‌های دریافتی وابسته است.

تفاوت از نظر یادگیری سیاست در Q-learning و SARSA.

Q-learning ارزش سیاست بهینه را یاد می‌گیرد و به اعمال عامل وابسته نیست. در مقابل، SARSA به یادگیری ارزش سیاستی که عامل در یک لحظه خاص دنبال می‌کند، متمرکز است.

این به این معناست که Q-learning می‌تواند بدون توجه به تصمیمات فعلی عامل، به دنبال بهترین نتایج ممکن باشد، در حالی که SARSA به طور مستقیم تحت تأثیر اعمال و پاداش‌هایی است که عامل در حین یادگیری دریافت می‌کند. این تفاوت در رویکرد یادگیری می‌تواند بر نحوه عملکرد و سرعت همگرایی هر الگوریتم تأثیر بگذارد.

در Q-learning، (off-policy) به موقعیت‌هایی اشاره دارد که یک عامل عملی را انتخاب می‌کند که توسط الگوریتم مشاهده نشده است.

روش خارج از سیاست (off-policy) به این معناست که مقدار Q به ارزش بهترین عمل ممکن در حالت بعدی به‌روزرسانی می‌شود، در حالی که به اعمالی که احتمالاً عامل انتخاب می‌کند، توجهی نمی‌شود.

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

کدام الگوریتم به سرعت به سیاست بهینه همگرا می‌شود؟

الگوریتم Q-learning به طور کلی به سیاست بهینه نزدیک‌تر همگرا می‌شود، زیرا تمایل دارد از عملگر بیشینه (max) برای پاداش‌های آینده مورد انتظار استفاده کند. با این حال، این ویژگی ممکن است بر پایداری الگوریتم تأثیر بگذارد.

به این معنا که اگرچه Q-learning می‌تواند سریع‌تر به یک سیاست بهینه دست یابد، اما این فرآیند ممکن است با نوسانات و عدم ثبات همراه باشد. این ناپایداری می‌تواند در مراحل اولیه یادگیری و در نتیجه اکتشافات تهاجمی بیشتر ایجاد شود. بنابراین، در حالی که 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

مقدمه

الگوریتم (State-Action-Reward-State-Action) SARSA در یادگیری تقویتی بر اساس سیاست، به عامل (Agent) کمک می‌کند تا بهینه عمل کند. این الگوریتم مقادیر ارزش (Q-Values) را برای هر ترکیب حالت-عمل به‌روزرسانی می‌کند. SARSA بر اساس حالت فعلی، عمل فعلی، پاداش دریافتی، حالت بعدی و عمل بعدی که از سیاست فعلی انتخاب شده، عمل می‌کند و با این روش، سیاست خود را به‌روزرسانی می‌کند.

یادگیری SARSA 

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

مفاهیم کلیدی در SARSA 

1.وضعیت (State) (s): وضعیتی است که عامل (Agent) در آن قرار دارد.

2.اقدام (Action) (a): عملی است که عامل (Agent) در حالت فعلی خود انجام می‌دهد

3.پاداش (Reward) (r): پاداشی است که عامل بعد از انجام یک عمل در یک حالت خاص دریافت می‌کند.

4.وضعیت بعدی (Next State) (s’): وضعیت جدیدی که عامل (Agent) پس از انجام یک عمل به آن منتقل می‌شود.

5.اقدام بعدی (Next Action) (a’): عملی که عامل (Agent) در حالت بعدی بر اساس سیاست (Policy) خود انجام می‌دهد.

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

نحوه کارکرد الگوریتم SARSA

SARSA به صورت گام‌به‌گام به این صورت عمل می‌کند:

1.انتخاب عمل (Action): عامل یک حالت اولیه (s) را انتخاب می‌کند و بر اساس یک سیاست (معمولاً

ϵ-greedy) عمل (a) انجام می‌دهد.

2.گرفتن پاداش و انتقال به حالت جدید: عامل با انجام این عمل، به حالت جدید (s′) می‌رود و پاداش (r) دریافت می‌کند.

3.انتخاب عمل بعدی: عامل در حالت جدید (s′) بر اساس همان سیاست یک عمل جدید (a′) را انتخاب می‌کند.

4.به‌روزرسانی Q-Value: سپس عامل از معادله زیر برای به‌روزرسانی Q-Value استفاده می‌کند:

که درآن:

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

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

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

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

r: پاداش فعلی که از محیط به عنوان پاسخ به عمل کنونی مشاهده می‌شود.

α: نرخ یادگیری (Learning Rate) که مشخص می‌کند عامل تا چه حد تغییرات را در Q-Value لحاظ کند. و مقدار آن بین 0 و 1 قرار دارد.

γ: ضریب تنزیل (Discount Factor) که نشان می‌دهد اهمیت پاداش‌های آینده به چه اندازه است که معمولا بین 0 و 1 است.

Q(s,a): مقدار Q فعلی برای حالت s و عمل a.

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

این فرمول مقدار Q را براساس پاداش دریافت‌شده و مقدار Q آینده به‌روزرسانی می‌کند.

در واقع، در  SARSA، سیاست جاری تصمیم می‌گیرد که در حالت بعدی کدام عمل a′  انجام شود و سپس مقدار Q(s,a)  بر این اساس به‌روزرسانی می‌شود. این وابستگی به سیاست جاری همان چیزی است که SARSA را به یک الگوریتم یادگیری روی سیاست (on-policy) تبدیل می‌کند.

5.تکرار مراحل: این فرآیند تا زمانی که عامل به حالت پایانی برسد، تکرار می‌شود.

در SARSA، برخلاف برخی الگوریتم‌های دیگر مانند Q-Learning که بر اساس بهترین عمل ممکن عمل می‌کند، به خاطر استفاده از همان سیاست (ϵ-greedy) که عامل عمل‌ها را انتخاب می‌کند، الگوریتم ارزش حالت و عمل آینده‌ای که احتمالاً عامل برمی‌گزیند را لحاظ می‌کند.

در تصویر زیر، شخصیتی به نام “عامل” (Agent) در دنباله‌ای از حالات (S و S’) اقداماتی (A و A’) انجام می‌دهد و پاداش‌هایی (R) دریافت می‌کند. فلش‌ها انتقال بین حالت‌ها، اقدامات و پاداش‌ها را نشان می‌دهند و مفهوم به‌روزرسانی مقادیر Q (Q-values) در هر مرحله را به تصویر می‌کشند.

مزایا SARSA

1.طبیعت الگوریتم‌های On-Policy:

SARSA یک الگوریتم on-policy است، به این معنی که بر اساس سیاستی که خود در حال دنبال کردن آن است، ارزیابی می‌کند. این ویژگی باعث می‌شود SARSA به سیاست فعلی حساس باشد و در محیط‌هایی که نیاز به کاهش ریسک دارند، عملکرد بهتری داشته باشد.

2.ایمنی بیشتر در محیط‌های تصادفی:

از آن‌جایی که SARSA به‌روزرسانی‌های خود را بر اساس اقداماتی که واقعاً انجام می‌دهد و جوایز واقعی که دریافت می‌کند، انجام می‌دهد، معمولاً در مقایسه با الگوریتم‌های off-policy مانند Q-learning محتاط‌تر عمل می‌کند. در محیط‌هایی که رفتارها تصادفی و غیرقابل پیش‌بینی هستند، این احتیاط باعث می‌شود که SARSA گزینه بهتری باشد.

3.فرآیند یادگیری ساده‌تر و روان‌تر:

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

4.تعادل میان کاوش و بهره‌برداری:

چون SARSA از اقداماتی که واقعاً انجام می‌دهد (که ممکن است شامل اقدامات کاوشی نیز باشد) استفاده می‌کند، به‌طور ذاتی بین کاوش (exploration) و بهره‌برداری (exploitation) تعادل برقرار می‌سازد. این ویژگی باعث می‌شود که SARSA برای محیط‌هایی که نیاز به آزمایش استراتژی‌های مختلف دارند، بسیار مناسب باشد.

معایب SARSA

1.همگرایی کندتر در محیط‌های قطعی:

از آن‌جایی که SARSA به‌روزرسانی‌های خود را بر اساس سیاست فعلی (که ممکن است شامل اقدامات کاوشی باشد) انجام می‌دهد، معمولاً در محیط‌های قطعی که نیاز به همگرایی سریع به سیاست بهینه دارند، نسبت به الگوریتم‌های off-policy مانند Q-learning کندتر عمل می‌کند.

2.حساسیت به سیاست کاوش:

عملکرد SARSA به شدت به استراتژی کاوش (مانند ε-greedy) وابسته است. اگر نرخ کاوش به‌درستی انتخاب نشود، ممکن است سیاست بهینه پیدا نشود و برای رسیدن به عملکرد مطلوب نیاز به تنظیمات بیشتری باشد.

3.محدودیت‌ الگوریتم‌های On-Policy:

به‌عنوان یک الگوریتم on-policy، SARSA تنها از اقداماتی که واقعاً انجام می‌دهد یاد می‌گیرد. اگر سیاستی که دنبال می‌کند بهینه نباشد، یادگیری SARSA نیز بهینه نخواهد بود. این ویژگی اجازه نمی‌دهد که SARSA از استراتژی‌های off-policy بهره‌برداری کند، استراتژی‌هایی که می‌توانند بر اساس بهترین اقدام ممکن به‌روزرسانی شوند.

4.سیاست‌های محتاطانه‌تر:

روش محتاطانه SARSA در به‌روزرسانی سیاست‌ها (با استفاده از اقدامات واقعی به جای اقدامات بهینه) می‌تواند منجر به سیاست‌هایی شود که محتاطانه‌تر عمل می‌کنند و در بلندمدت نتایج بهینه‌ای به همراه نداشته باشند.

5.حساسیت بالا به تنظیمات در محیط‌های پیچیده:

اگرچه SARSA نسبتاً ساده است و نیاز به تنظیمات کمتری دارد، در محیط‌های پیچیده و پرچالش، تنظیمات پارامترهای یادگیری، نرخ تنزیل و پارامترهای کاوش نیاز به دقت بیشتری دارند تا از ناپایداری یا یادگیری کند جلوگیری شود.

کاربردهای SARSA

SARSA به‌ویژه در سناریوهایی که نیاز به اتخاذ تصمیمات محتاطانه و پرهیز از ریسک‌های زیاد وجود دارد، مفید است. برخی از کاربردهای رایج SARSA عبارتند از:

1.یافتن مسیر و ناوبری در محیط‌های پیچیده:

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

2.مدیریت کنترل ربات‌ها:

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

3.کاربردهای مالی:

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

4.بازی‌های با المان‌های تصادفی و غیرقابل پیش‌بینی

SARSA معمولاً در بازی‌هایی که نتایج تصادفی دارند (مانند بازی‌هایی که در آن‌ها تاس انداخته می‌شود یا رویدادهای تصادفی در جریان هستند) استفاده می‌شود. در این‌گونه محیط‌ها، حساسیت SARSA به سیاست کاوش می‌تواند آن را نسبت به دیگر روش‌ها، مانند Q-learning، بهتر کند.

5.سیستم‌های مدیریت انرژی:

در سیستم‌های مدیریت انرژی، مانند شبکه‌های هوشمند یا سیستم‌های ذخیره‌سازی باتری، SARSA می‌تواند به مدیریت توزیع انرژی کمک کرده و از مصرف منابع اضافی یا ناکافی جلوگیری کند.

6.برنامه‌ریزی درمانی در حوزه مراقبت‌های بهداشتی:

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

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

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-table چیست؟

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

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

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

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

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

Q-table 

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

توضیحات جدول

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

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

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

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

5.برنامه‌های درمانی شخصی‌سازی‌شده (Personalized Treatment Plans): در حوزه پزشکی، از 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 یکی از شناخته‌شده‌ترین و ساده‌ترین الگوریتم‌ها برای حل مسائلی است که با فرآیندهای تصمیم‌گیری مارکوف (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 به دنبال پاسخ به این سؤال است: “در هر وضعیت، کدام اقدام بیشترین ارزش را دارد و به تصمیم‌گیری بهینه منجر می‌شود؟”

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

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

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

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

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

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

این تصویر الگوریتم 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.نوشتن ماتریس انتقال احتمالات :

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

• حالت آفتابی (S)
• حالت ابری (C)
• ماتریس انتقال احتمالات P به صورت روبرو است :

• SSP یعنی احتمال اینکه فردا آفتابی باشد ، اگر امروز آفتابی باشد.
• SCP یعنی احتمال اینکه فردا ابری باشد ، اگر امروز آفتابی باشد.
• CSP یعنی احتمال اینکه فردا آفتابی باشد ، اگر امروز ابری باشد.
• CCP یعنی احتمال اینکه ابری آفتابی باشد ، اگر امروز ابری باشد.

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

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

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

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

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

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

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

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

مثال عملی :

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

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

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

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

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

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

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

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

نتیجه‌گیری

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

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

نمونه‌ای از زنجیره مارکوف چیست ؟

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

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

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

Hello = [ “Everyone” , “” , “Everyone” , “There” , “There” , “There” , “There” , “There” ,…]

 اگر در لیست بالا ۲۰ کلمه وجود داشته باشد که هر کدام پس از کلمه “سلام” (Hello) آمده باشد، آنگاه احتمال وقوع هر کلمه طبق فرمول زیر محاسبه می‌شود:

P(word) = Frequency of word / total Number of Words in List

P(Everyone) = 9/20

P(,) = 1/20

P(There) = 10/20

بردار حالت اولیه نشان‌دهنده احتمال شروع جمله با هر یک از کلمات ممکن است. در مثال بالا، از آنجا که “سلام” (Hello) تنها کلمه‌ای است که می‌توانید با آن شروع کنید، بردار حالت اولیه یک بردار Nx1 خواهد بود که ۱۰۰ درصد احتمال به کلمه “سلام” اختصاص داده شده است. با استفاده از این بردار، می‌توانید حالت‌های آینده را از طریق این مدل مارکوف پیش‌بینی کنید.

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

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

1.هواشناسی:

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

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

مثال: اگر امروز هوا آفتابی است ، زنجیره مارکوف می‌گوید ۸۰٪ احتمال است که فردا هم آفتابی باشد، و ۲۰٪ احتمال دارد بارانی باشد.

2.تشخیص صدا و گفتار:

در گوشی‌های موبایل، وقتی از سیری یا google assistant سؤال می‌پرسید، این سیستم‌ها از زنجیره مارکوف استفاده می‌کنند تا بفهمند هر کلمه‌ای که می‌گویید به چه کلمه‌ی بعدی ممکن است مربوط باشد. به عبارت دیگر، صدای شما را با استفاده از مدل مارکوف تجزیه و تحلیل می‌کنند.

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

• مثال: اگر گفتید “سلام”، احتمال زیادی دارد که کلمه بعدی “خوبی” باشه، نه “موبایل”.

3.بازاریابی و تحلیل رفتار مشتری:

• 

• شرکت‌ها با استفاده از زنجیره مارکوف، رفتار مشتری‌ها رو پیش‌بینی می‌کنند. مثلاً وقتی شما محصولی را خریداری می‌کنید، زنجیره مارکوف می‌گوید بعد از آن ممکن است که چه محصول دیگری را خریداری کنید.
• چطور کاربرد دارد؟ شرکت‌ها از زنجیره مارکوف استفاده می‌کنند تا بفهمند بعد از خرید یک محصول، مشتری چه چیزی را ممکن است بعد از آن خریداری کند . این کار با ساختن مدل مارکوف برای رفتار مشتری‌ها انجام می‌شود. برای هر محصول، احتمال خرید محصول بعدی بر اساس محصول قبلی مشخص می‌شود.
• مثال: اگر مشتری کتابی درباره “آموزش پایتون” خرید، زنجیره مارکوف می‌تواند پیش‌بینی کند احتمال اینکه بعدش کتاب “پروژه‌های پایتون” رو خریداری کند بیشتر است.

4.مالی و بورس:

• 

• در بازار بورس، از زنجیره مارکوف استفاده می‌شود تا قیمت سهام یا ارزها رو پیش‌بینی کنند. یعنی مثلاً اگر قیمت سهام امروز بالا رفته باشد، می‌توانند احتمال دهند که فردا قیمت بالا می‌ماند یا خیر.
• چطور کاربرد دارد؟ در بازار بورس، قیمت سهام به وضعیت فعلی بازار بستگی دارد. زنجیره مارکوف کمک می‌کند که پیش‌بینی کنیم فردا قیمت سهام چطوری تغییر می‌کند. مثلاً اگر امروز سهام بالا رفته است، زنجیره مارکوف با استفاده از احتمالات می‌تواند پیش‌بینی کند که فردا چقدر احتمال دارد قیمت بیشتر بره بالا یا پایین بیاید.
• مثال: اگر امروز قیمت سهام زیاد شده است، زنجیره مارکوف می‌گوید ۶۰٪ احتمال دارد فردا هم بالا برود، ولی ۴۰٪ احتمال داره پایین بیاد.

5.مدیریت صف‌ها:

• در بانک‌ها یا بیمارستان‌ها، زنجیره مارکوف می‌تواند پیش‌بینی کند که در چه ساعاتی صف طولانی‌تر میشود. مثلاً اگر الان صف کوتاه است، یک ساعت بعد صف احتمال دارد چقدر طولانی شود؟
• چطور کاربرد دارد؟ در بانک یا بیمارستان، با استفاده از زنجیره مارکوف می‌توانند پیش‌بینی کنند که در چه زمانی صف طولانی‌تر می‌شود. مثلاً اگر الان تعداد مراجعین کم است، زنجیره مارکوف می‌تواند پی‌بینی کند در یک ساعت آینده صف شلوغ‌تر میشود یا خیر.
• مثال: اگر الان در بانک فقط ۵ نفر در صف قرار دارند، زنجیره مارکوف می‌گوید ۷۰٪ احتمال دارد که در ۳۰ دقیقه آینده تعداد افراد بیشتر شود.

6.مهندسی ژنتیک و بیولوژی:

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

7.تشخیص چهره و تصویر

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

8.الگوریتم PageRank گوگل

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

9.فیلتر کالمن (Kalman Filter)

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

10.پردازش زبان طبیعی (NLP) :

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

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

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.حل تحلیلی (Analytical Solution)

2.روش ماتریس انتقال (Transition Matrix Method)

3.شبیه‌سازی مونت کارلو (Monte Carlo Simulation)

4.روش مقدار ویژه (Eigenvalue Method)

5.روش گاوس-سایدل (Gauss-Seidel Method)

6.روش تکراری (Iterative Methods)

7.الگوریتم ول‌من (Value Iteration Algorithm)

8. روش برنامه ریزی پویا (Dynamic Programming – DP)

9.روش بلمن-فورد(Bellman-Ford Algorithm)

10.ارزش گذاری(Value Iteration)

11.سیاست گذاری تکراری (Policy Iteration)

12.الگوریتم سیاست ثابت (Policy Iteration Algorithm)

13.روش شبیه سازی و بهینه سازی (Simulation and Optimization)

14.روش های یادگیری تقویتی (Reinforcement Learning Methods)

15.روش زنجیره مارکوف پنهان (Hidden Markov Models – HMM)

1.حل تحلیلی(Analytical Solution)

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

مثال:

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

با استفاده از حل تحلیلی، می‌توانیم محاسبه کنیم که در بلندمدت چه درصد از روزها آفتابی، ابری، یا بارانی خواهد بود.

2.روش ماتریس انتقال (Transition Matrix Method)

این روش با استفاده از ماتریس انتقال احتمالات بین حالت‌ها حل می‌شود. هر ورودی ماتریس نشان می‌دهد که با چه احتمالی از یک حالت به حالت دیگر تغییر می‌کنیم.

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

3.شبیه سازی مونت کارلو (Monte Carlo Simulation)

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

به عنوان مثال، اگر بخواهیم بدانیم در طول ۱۰۰ روز وضعیت هوا چگونه خواهد بود، می‌توانیم چندین بار وضعیت‌ها را به‌صورت تصادفی شبیه‌سازی کنیم و ببینیم که مثلا، چه درصدی از روزها آفتابی، ابری یا بارانی بوده است.

4.روش مقدار ویژه (Eigenvalue Method)

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

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

5.روش گاوس-سایدل (Gauss-Seidel Method)

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

به عنوان مثال، در محاسبات پیچیده، اگر بخواهیم به‌سرعت‌تر به پاسخ برسیم، این روش به ما کمک می‌کند تا وضعیت‌های آینده را پیش‌بینی کنیم.

6.روش تکراری (Iterative Methods)

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

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

7.الگوریتم ول من (Value Iteration Algorithm)

این روش برای حل مسائل تصمیم‌گیری مارکوف (MDP) استفاده می‌شود. هدف این الگوریتم، یافتن بهترین سیاست (Policy) برای یک سیستم است که سود یا پاداش بلندمدت را بیشینه کند.

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

8.روش برنامه ریزی پویا (Dynamic Programming – DP)

این روش‌ها زمانی استفاده می‌شوند که مدل MDP و قوانین انتقال حالت‌ها مشخص باشند.

معادله بلمن (Bellman Equation)

معادله بلمن یکی از اصلی‌ترین روش‌های حل مسائل تصمیم‌گیری مارکوف (MDP) است. در این روش، هدف یافتن تابع ارزش (Value Function) برای هر حالت می‌باشد. این معادله یکی از پایه‌های یادگیری تقویتی (Reinforcement Learning) است و برای درک ارزش یک حالت در محیط استفاده می‌شود.

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

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

فرمول ساده آن برای هر حالت به شکل زیر است:

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

حالا، شما می‌خواهید بدانید که ارزش رفتن به هر اتاق (یا همان حالت) چقدر است. ارزش یک اتاق (حالت) به دو چیز بستگی دارد:

1.پاداشی که در همان لحظه در آن اتاق دریافت می‌کنید R(s)

2.احتمال این که بعد از رفتن به آن اتاق، به اتاق‌های دیگری هم بروید و از آن‌ها هم پاداش بگیرید. (این همان بخشی است که داریم احتمال رسیدن به اتاق بعدی رو حساب می‌کنیم، که این را با P(s′,s,a) نشان می‌دهیم).

فرمول بلمن به شما می‌گوید که ارزش یک اتاق (یا همان حالت) برابر با جمع این دو چیز است:

1.پاداشی که همون لحظه دریافت میکنید R(s)

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

اینکه جمع آن‌ها چقدر است، به مامی‌گوید که رفتن به آن اتاق (یا حالت) چقدر خوب است.

V(s) ارزش حالت فعلی است.

R(s,a, s′) پاداش دریافتی برای رفتن از حالت s به حالت s′ با اقدام a.

γ(گاما): ضریب تخفیف که اهمیت پاداش‌های آینده را مشخص می‌کند  . این عدد تعیین می‌کنه که چقدر به پاداش‌های آینده اهمیت دهیم. اگر γ زدیک ۰ باشه، یعنی فقط به پاداش‌های حال اهمیت دهیم؛ اگه نزدیک ۱ باشد، یعنی پاداش‌های آینده‌هم اهیمت دارند.

P(s′,s,a): احتمال رفتن به حالت s′ با انجام عمل a در حالت s

V(s′) ارزش حالت بعدی است.

این معادله را برای همه حالت‌ها حل می‌کنیم تا بهترین سیاست را پیدا کنیم.

مثال :

فرض کنید در هزارتو (Maze) هستید. وقتی در اتاق (حالت s) ایستادید :

• می‌دانید که ۵ سکه در آنجا روی زمین است (این R(s) می‌شود)
• اما از آن اتاق ممکن است به اتاق‌های دیگری بروید که در آن‌ها هم سکه وجود دارد. در این بخش، باید ببینید احتمال رسیدن به اتاق‌های دیگر چقدر است. (این همون P(s′,s,a) می‌شود) و اگر به آن اتاق‌ها برسید، چند سکه دیگر دریافت می‌کنید (این V(s′) است.)

کاربرد معادله بلمن کجاست؟

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

• بازی‌های کامپیوتری: برای برنامه‌ریزی اینکه یک کاراکتر چگونه از موانع عبور کند و امتیاز بیشتری دریافت کند. (هوش مصنوعی در بازی‌ها می‌تواند با استفاده از این معادله تصمیم بگیرد که بهترین حرکت در هر لحظه چیست.)

• رباتیک: برای اینکه ربات‌ها بتوانند راه‌هایی را انتخاب کنند که سریع‌تر به مقصد برسند و انرژی کمتری مصرف کنند. (همچنین در طراحی ربات‌ها برای یادگیری راه‌های بهینه، مانند پیدا کردن مسیر بهینه در یک محیط پیچیده.)

اقتصاد و مالی: برای تصمیم‌گیری‌های سرمایه‌گذاری که کدام سهام یا دارایی بیشترین سود را در طول زمان دارد.

• کنترل هوشمند: در سیستم‌های کنترل، مانند هواپیماها یا خودروهای خودران، معادله بلمن کمک می‌کند تا سیستم بهترین تصمیم‌ها را بگیرد و بهینه‌ترین مسیرها را انتخاب کند.

چرا معادله بلمن خوب است؟

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

کاربرد در الگوریتم‌ها :

معادله بلمن در چندین الگوریتم و روش‌های مختلف یادگیری تقویتی (Reinforcement Learning) به کار می‌رود. این معادله پایه‌ای برای محاسبه ارزش حالت‌ها (state values) و تصمیم‌گیری در محیط‌های مختلف است.

1.برنامه ریزی پویا (Dynamic Programming)

• الگوریتم Policy Iteration :

این الگوریتم در دو مرحله کار می‌کند:

1.Evaluation: ارزش هر حالت (value) با استفاده از معادله بلمن محاسبه می‌شود.

2.Improvement: با استفاده از این ارزش‌ها، سیاست (policy) بهبود داده می‌شود تا انتخاب عمل‌هایی (actions) که به حالت‌های بهتر منجر می‌شوند، تقویت شوند.

• از معادله بلمن استفاده می‌شود تا بفهمیم در هر مرحله کدام حالت بهتر است و چگونه باید سیاست را تغییر دهیم.
• الگوریتم Value Iteration:

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

معادله بلمن در اینجا برای به‌روزرسانی مکرر ارزش‌ها استفاده می‌شود تا به مجموعه‌ای از ارزش‌های بهینه برسیم.

2.Q-Learning:

معادله بلمن Q

در Q-Learning، به جای اینکه فقط ارزش حالت‌ها را بذانیم ، می‌خواهیم بدانیم هر عمل (action) در هر حالت چقدر خوب است. در اینجا به جای ارزش حالت، ارزش Q  (ا Q-value) داریم که نشان می‌دهد هر حالت و عمل چقدر بهینه است.

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

Q-Learning از معادله بلمن استفاده می‌کند تا با به‌روزرسانی Q-value‌ها بفهمیم کدام عمل بهترین نتیجه را به همراه دارد.

3.SARSA (State-Action-Reward-State-Action):

معادله بلمن برای به‌روزرسانی Q-value :

SARSA هم مثل Q-Learning کار می‌کند ولی به جای اینکه از بیشترین Q-value استفاده کند، از سیاستی که همان لحظه در اختیار دارد پیروی می‌کند ، استفاده می‌کند. معادله SARSA مشابه Q-Learning است اما با استفاده از معادله بلمن به صورت متفاوتی به‌روزرسانی می‌شود.

4.DQN (Deep Q-Networks):

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

چرا از معادله بلمن استفاده می‌کنند؟

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

2.رویکرد بازگشتی (Recursive) : معادله بلمن به شکل بازگشتی کار می‌کند و این باعث می‌شود به راحتی ارزش حالت‌ها را در طول زمان و با تکرار به‌روزرسانی کنیم. این تکرار باعث می‌شود که ارزش بهینه رو پیدا کنیم.

3.فاکتور کردن پاداش‌های آینده: یکی از ویژگی‌های مهم این معادله، استفاده از فاکتور تخفیف (γ) برای محاسبه پاداش‌های آینده است. این یعنی می‌توانیم تصمیمات حال را نه فقط بر اساس پاداش لحظه‌ای بلکه با در نظر گرفتن پاداش‌های آینده بگیریم.

در نهایت، معادله بلمن کمک می‌کند که در مسائل پیچیده، بهترین و بهینه‌ترین تصمیم رو بگیریم.

9.روش بلمن-فورد(Bellman-Ford Algorithm)

این روش بیشتر برای مسائل گراف‌ها استفاده می‌شود و کمک می‌کند تا کوتاه‌ترین مسیر یا کمترین هزینه را در گراف‌هایی که دارای وزن‌های منفی هم هستند پیدا کنیم.

مثال:

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

10.ارزش گذاری(Value Iteration)

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

مراحل کار:

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

مثال:

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

11.سیاست گذاری تکراری (Policy Iteration)

در این روش به‌جای تمرکز بر ارزش حالت‌ها، سیاست (Policy) را بهبود می‌دهیم. سیاست یعنی “برای هر حالت چه عملی انجام دهیم؟”. این روش شامل دو مرحله است:

1.ارزیابی سیاست: ابتدا ارزش حالات را با سیاست فعلی محاسبه می‌کنیم.

2.بهبود سیاست: سپس سیاست را طوری تغییر می‌دهیم که پاداش بهتری بگیریم.

این فرآیند تکرار می‌شود تا به یک سیاست بهینه برسیم.

مثال:

در بازی‌ها، سیاست شما می‌تواند این باشد که مثلاً همیشه به جلو بروید. سپس بررسی می‌کنید که این سیاست چقدر خوب است و با تغییر سیاست به “گاهی به جلو و گاهی به عقب بروید”، پاداش بهتری بگیرید.

12.الگوریتم سیاست ثابت (Policy Iteration Algorithm)

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

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

13.روش شبیه سازی و بهینه سازی (Simulation and Optimization)

این روش با شبیه‌سازی وضعیت‌های مختلف سیستم و پیدا کردن بهترین حالت ممکن، بهینه‌سازی می‌کند. این روش معمولاً برای مسائل پیچیده‌ای که تحلیل دقیق آن‌ها سخت است استفاده می‌شود.

مثال:

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

14.روش های یادگیری تقویتی (Reinforcement Learning Methods)

در این روش‌ها، یک عامل (Agent) با تعامل با محیط یاد می‌گیرد که با انجام کارهای مختلف، بیشترین پاداش را کسب کند. این روش برای مسائل تصمیم‌گیری و مارکوف استفاده می‌شود.

مثال:

یک ربات را در نظر بگیرید که در حال یادگیری است که چگونه از یک مسیر پر از موانع عبور کند. ربات با آزمون و خطا یاد می‌گیرد که بهترین تصمیم‌ها چیست.

15.روش زنجیره مارکوف پنهان (Hidden Markov Models – HMM)

این روش برای مسائلی استفاده می‌شود که حالت واقعی سیستم قابل مشاهده نیست و فقط اطلاعات محدودی از وضعیت داریم. با HMM می‌توانیم پیش‌بینی کنیم که سیستم در چه حالتی است.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

زنجیره مارکوف چیست ؟

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

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

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

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

از اهداف این مدل:

• آینده فقط به وضعیت فعلی وابسته است.
• اطلاعات گذشته‌های دورتر اهمیت ندارد.
• مدل‌سازی و پیش‌بینی را ساده‌تر می‌کند.

اصل زنجیره مارکوف

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

سه مفهوم اصلی که نشان میدهد زنجیره ما مارکوف است:

1.خاصیت مارکوف (Markov Property) :

این خاصیت بیان می‌کند که برای پیش‌بینی وضعیت آینده، تنها وضعیت کنونی کافی است و نیازی به دانستن تاریخچه‌ی وضعیت‌ها نیست. به عبارت دیگر :

این یعنی احتمال اینکه گام x باشد فقط به مرحله n بستگی دارد نه توالی کامل مراحل قبل از n .

برای مثال یک رستوران سه نوع غذا درست می‌کند : پیتزا ، همبرگر و هات داگ

فرض کنید این رستوران روز اول همبرگر و روز دوم پیتزا و روز سوم بازهم پیتزا درست میکند . حالا این احتمال چقدر است که این رستوران در روز چهارم هات داگ درست بکند ؟

برای اینکه بفهمیم چقدر احتمال دارد که فردا هات داگ درست بکند باید به روز قبلش نگاه بکنیم :

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

2.حالت‌های قطعی (Discrete States) :

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

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

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

3.انتقال احتمال (Transition Probability) :

هر زنجیره مارکوف دارای یک ماتریس انتقال است که مقادیر آن نشان‌دهنده‌ی احتمال انتقال از یک حالت به حالت دیگر است.

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

این سه مفهوم، اساس فهم و تحلیل زنجیره‌های مارکوف را تشکیل می‌دهند .

ویژگی اصلی زنجیره مارکوف چیست ؟

• همان‌طور که پیش‌تر اشاره شد، فرآیند مارکوف یک فرآیند تصادفی است که دارای ویژگی بدون حافظه (memoryless) می‌باشد. در ریاضیات، اصطلاح «بدون حافظه» به خاصیتی در توزیع‌های احتمالی اشاره دارد. به‌طور کلی، این ویژگی به سناریوهایی مربوط می‌شود که زمان وقوع یک رویداد خاص، وابسته به مدت زمانی که تاکنون سپری شده است، نیست. به عبارت دیگر، وقتی یک مدل خاصیت بدون حافظه دارد، به این معناست که مدل «فراموش کرده» است که در کدام وضعیت

  

  سیستم قرار دارد. بنابراین، حالت‌های قبلی فرآیند تأثیری بر احتمالات نخواهند داشت.

• ویژگی اصلی یک فرآیند مارکوف همین خاصیت بدون حافظه است. پیش‌بینی‌های مرتبط با فرآیند مارکوف، مشروط به وضعیت فعلی آن هستند و مستقل از حالت‌های گذشته و آینده‌اند.
• این ویژگی بدون حافظه در مدل مارکوف می‌تواند هم یک مزیت و هم یک محدودیت باشد. به‌عنوان مثال، تصور کنید می‌خواهید کلمات یا جملاتی را بر اساس متنی که قبلاً وارد کرده‌اید پیش‌بینی کنید — دقیقاً مانند کاری که گوگل برای جی‌میل انجام می‌دهد.
• اما نقطه ضعف این روش این است که نمی‌توانید متنی را پیش‌بینی کنید که بر اساس زمینه‌ای از حالت قبلی مدل باشد. این یک مشکل رایج در پردازش زبان طبیعی (Natural Language Processing یا NLP) است و بسیاری از مدل‌ها با این چالش مواجه‌اند.

اجزای زنجیره‌ی مارکوف

1.وضعیت‌ها (States)

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

• ماشین خاموش
• ماشین روشن
• ماشین در حال کار

2.عمل (Action)

اقداماتی که می‌توان در هر حالت انجام داد.

3.انتقال‌های حالت (State Transitions)

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

برای مثال، اگر ماشین روشن باشد، احتمال اینکه خاموش شود 30% و احتمال اینکه در حال کار باشد 70% است.

4.ماتریس انتقال (Transition Matrix)

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

این ماتریس نشان می‌دهد که اگر ماشین در حال کار باشد، احتمال اینکه در آینده روشن شود 30% و احتمال اینکه خاموش شود 10% است.

5.پاداش (Reward)

مقادیری که به عمل‌ها یا وضعیت‌ها نسبت داده می‌شود و نشان می‌دهد که چقدر از انجام یک عمل در یک حالت راضی هستیم.

6.سیاست (Policy)

راهنمایی برای تصمیم‌گیری که در هر حالت چه عملی انجام شود.

7.تابع ارزش (Value Function)

تابعی که ارزش هر حالت را تعیین می‌کند و نشان می‌دهد که چه میزان پاداش می‌توان از آن حالت کسب کرد.

8.تابع مدل (Model Function)

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

9.توزیع اولیه (Initial Distribution)

مشخص می‌کند از کدام حالت شروع می‌شود.به عنوان مثال، اگر ماشین به طور تصادفی روشن شود، احتمال اینکه ماشین در ابتدا خاموش باشد 50%، روشن 30% و در حال کار 20% است.

10.حالت‌های نهایی (Terminal States)

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

این اجزا به طور کلی به ما کمک می‌کنند تا فرایند مارکوف را مدل‌سازی و تحلیل کنیم.

مثال آب و هوا :

فرض کنیم که آب و هوای هر روز فقط به آب و هوای روز قبل بستگی دارد و تأثیری از روزهای قبل‌تر نمی‌گیرد.

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

1. اگر امروز آفتابی باشد:

• احتمال اینکه فردا هم آفتابی باشد 30% است.
• احتمال اینکه فردا بارانی باشد 70% است.

2. اگر امروز بارانی باشد:

• احتمال اینکه فردا آفتابی باشد 50% است.
• احتمال اینکه فردا هم بارانی باشد 50% است.

در این نمودار، فلش‌ها نشان‌دهنده انتقال بین حالات مختلف آب و هوا و اعداد روی فلش‌ها بیانگر احتمال وقوع هر انتقال هستند .

ماتریس انتقال

مجموع احتمالات در هر سطر باید برابر با 1 باشد، چرا که احتمال همه حالات ممکن است.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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