کیو-یادگیری

در اینجا مدل مسئله تشکیل شده از یک عامل، وضعیت‌ها S و مجموعه از اقدامات A برای هر وضعیت.با انجام یک اقدام ${\displaystyle a\in A}$

${\displaystyle Q:S\times A\to \mathbb{R}}$

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

${\displaystyle Q(s_t,a_t)\leftarrow \underset{\mathrm{o}\mathrm{l}\mathrm{d}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}}{\underbrace{Q(s_t,a_t)}}+\underset{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e}}{\underbrace{{\alpha }_t(s_t,a_t)}}\times \left[\stackrel{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}\mathrm{e}\mathrm{d}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}}{\overbrace{\underset{\mathrm{r}\mathrm{e}\mathrm{w}\mathrm{a}\mathrm{r}\mathrm{d}}{\underbrace{R(s_t)}}+\underset{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}}{\underbrace{\gamma }}\underset{\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{f}\mathrm{u}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}}{\underbrace{\underset{a_{t+1}}{max}Q(s_{t+1},a_{t+1})}}}}-\underset{\mathrm{o}\mathrm{l}\mathrm{d}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}}{\underbrace{Q(s_t,a_t)}}\right]}$

که ${\displaystyle R(s_t)}$

فرمول فوق معادل عبارت زیر است: ${\displaystyle Q(s_t,a_t)\leftarrow Q(s_t,a_t)(1-{\alpha }_t(s_t,a_t))+{\alpha }_t(s_t,a_t)[R(s_t)+\gamma \underset{a_{t+1}}{max}Q(s_{t+1},a_{t+1})]}$

یک اپیزود الگوریتم وقتی ${\displaystyle s_{t+1}}$

نرخ یادگیری

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

عامل تخفیف

عامل تخفیف اهمیت پاداش‌های آینده را تعیین می‌کند. مقدار صفر باعث می‌شود عامل ماهیت فرصت طلبانه گرفته و فقط پاداش‌های فعلی را مد نظر قرار می‌دهد. در حالی که مقدار یک عامل را ترغیب می‌کند برای یک دوره زمانی طولانی برای پاداش تقلا کند. اگر این عامل، یک یا بیشتر از یک باشد مقادیر ${\displaystyle Q}$

شرایط اولیه (Q_0)

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

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

تخمین‎گر تابع

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

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

گسسته سازی(Quantization)

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

کیو-یادگیری اولین بار توسط واتکینز معرفی شد. in 1989. برهان همگرایی بعداً توسط واتکینز و دایان ارائه شد. in 1992.

واتکینز اولین بار در مقاله ای با عنوان "یادگیری از پاداش تاخیری" در رساله ی دکترایش به این موضوع اشاره کرد.هشت سال زودتر در سال 1981 مسئله ای با عنوان "یادگیری تقویتی تاخیری" توسط بولونسزکی حل شد.

درسال2014 تیم گوگل دیپ مایند یادگیری کیو را با یادگیری عمیق ترکیب کرد و با نام "یادگیری عمیق کیو" منتشر کرد که می توانست بازی آتاری3600 را در سطح انسان بازی کند.

یادگیری عمیق کیو

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

یادگیری دوگانه کیو

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

این روش، دو ماتریس کیو دارد که هردو بوسیله ی تجربیات مجزا و مستقل از یکدیگر آموزش دیده اند:

${\displaystyle Q_{t+1}^A(s_t,a_t)=Q_t^A(s_t,a_t)+{\alpha }_t(s_t,a_t)\left(r_t+\gamma Q_t^B\left(s_{t+1},\underset{a}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}{Q}_t^A(s_{t+1},a)\right)-Q_t^A(s_t,a_t)\right)}$

${\displaystyle Q_{t+1}^B(s_t,a_t)=Q_t^B(s_t,a_t)+{\alpha }_t(s_t,a_t)\left(r_t+\gamma Q_t^A\left(s_{t+1},\underset{a}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}{Q}_t^B(s_{t+1},a)\right)-Q_t^B(s_t,a_t)\right).}$

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

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

• Q-Learning topic on Knol
• Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England.
• Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning
• Q-Learning by Examples
• Reinforcement Learning: An Introduction by Richard Sutton and Andrew S. Barto, an online textbook. See "6.5 Q-Learning: Off-Policy TD Control".
• Connectionist Q-learning Java Framework
• Piqle: a Generic Java Platform for Reinforcement Learning
• Reinforcement Learning Maze, a demonstration of guiding an ant through a maze using Q-learning.
• Q-learning work by Gerald Tesauro
• Q-learning work by Tesauro Citeseer Link
• Q-learning algorithm implemented in processing.org language
• Example java applet for pole balancing in 2D with source code