Q-Learning و یادگیری تقویتی — خودآموز سریع و جامع

آخرین به‌روزرسانی: ۱۵ مرداد ۱۴۰۰
زمان مطالعه: ۸ دقیقه

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

  • Q-Learning چیست؟
  • چگونه می‌توان این الگوریتم را با استفاده از کتابخانه Numpy پیاده‌سازی کرد؟

مساله: شوالیه و پرنسس

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

Q-Learning

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

  • شوالیه در هر گام ۱- امتیاز از دست می‌دهد (از دست دادن امتیازها در هر گام به عامل کمک می‌کند تا سریع‌تر باشد).
  • اگر شوالیه یک دشمن را لمس کند، ۱۰۰- امتیاز از دست می‌دهد و اپیزود به پایان می‌رسد.
  • اگر شوالیه در قلعه باشد، برنده شده و ۱۰۰+ امتیاز دریافت میکند.

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

Q-Learning

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

معرفی Q-table

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

Q-Table

به منظور انجام محاسبات، این شبکه به یک جدول تبدیل می‌شود. جدول ساخته شده، Q-table نامیده می‌شود (Q سرنام quality است و مربوط به عبارت quality of the action). ستون‌ها چهار عمل (چپ، راست، بالا و پایین) هستند. سطرها حالت‌ها هستند. مقدار هر سلول بیشینه پاداش آینده مورد انتظار برای حالت داده شده و عمل است.

Q-Table

هر امتیاز Q-table، پاداش آینده مورد انتظار بیشینه‌ای است که شوالیه در صورت عمل کردن با بهترین سیاست داده شده، به آن دست می‌یابد. به این Q-table می‌توان به صورت بازی «برگه تقلب» نگاه کرد. به لطف این جدول، شوالیه با نگاه کردن به بالاترین امتیاز در هر سطر برای هر حالت، می‌داند که بهترین عمل قابل انجام چیست. به نظر می‌رسد مساله قلعه حل شده است! اما اکنون چطور باید ارزش را برای هر جز Q-Table محاسبه کرد؟!

الگوریتم Q-learning: یادگیری تابع ارزش عمل

تابع ارزش عمل (یا Q-function) دو ورودی حالت و عمل را دریافت می‌کند. سپس، پاداش آینده مورد انتظار برای آن حالت و عمل را باز می‌گرداند.

Q-Function

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

Q-function

پیش از آنکه شوالیه در محیط جست‌و‌جو کند، Q-table مقادیر دلخواه مشابهی (اغلب اوقات ۰) را ارائه می‌کند. با جست‌و‌جوی شوالیه در محیط، Q-table تخمین بهتر و بهتری را با به روز رسانی بازگشتی (Q(s,a با استفاده از «معادله بلمن» (Bellman Equation) در اختیار قرار می‌دهد.

فرآیند الگوریتم Q-learning

Q-Learning-FlowChart

شبه کد الگوریتم Q-Learning

  • مقداردهی اولیه Q-value‌ها ((Q(s,a) با ارزش‌های دلخواه برای همه جفت‌های حالت-عمل
  • برای زندگی یا تا هنگامی که یادگیری متوقف شود
  • عمل (a) را در حالت (s) کنونی جهان بر اساس تخمین کنونی Q-value (یعنی (Q(s,a) انتخاب کن
  • عمل (a) را انجام بده و حالت خروجی (’s) و پاداش (r) را مشاهده کن
  • Q-Learning-Pseudo-Code را به روز رسانی کن

گام ۱: مقداردهی اولیه ارزش‌های Q

Q-table با m ستون (m = تعداد اعمال) و n سطر (n = تعداد حالت‌ها) ساخته شد. اکنون مقداردهی اولیه با «۰» انجام می‌شود.

Q-Learling

گام ۲: برای زندگی (یا تا هنگامی که یادگیری متوقف شد)

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

گام ۳: انتخاب یک عمل

انتخاب یک عمل a در وضعیت کنونی s برمبنای ارزش کنونی Q-value تخمین زده شده.

اما، اگر همه Q-value‌ها برابر با صفر باشند، شوالیه کدام عمل را در ابتدا انجام خواهد داد؟ توازن بین جست‌و‌جو و استخراج که در قسمت پیشین در رابطه با آن صحبت شد، اکنون حائز اهمیت می‌شود. ایده آن است که در آغاز، از «استراتژی حریصانه اپسیلون» (epsilon greedy strategy) استفاده شود.

  • یک نرخ جست‌و‌جوی «اپسیلون» تعیین می‌شود که در آغاز برابر با یک قرار داده می‌شود. این، نرخ گام‌هایی است که شوالیه به طور تصادفی انجام می‌دهد. در آغاز، این مقدار باید بیشترین ارزش ممکن باشد، زیرا شوالیه هیچ چیز درباره ارزش‌های موجود در Q-table نمی‌داند. این یعنی نیاز به جست‌و‌جوهای زیاد و انتخاب تصادفی اعمال توسط او است.
  • یک عدد تصادفی تولید می‌شود. اگر این عدد بزرگ‌تر از اپسیلون بود، استخراج انجام می‌شود (این یعنی از آنچه در حال حاضر مشخص است برای انتخاب بهترین عمل در هر گام استفاده می‌شود). در غیر این صورت، جست‌و‌جو صورت می‌پذیرد.
  • ایده آن است که باید یک اپسیلون بزرگ در ابتدای راه آموزش Q-function وجود داشته باشد. سپس، به تدریج و پس از آنکه اطمینان عامل در تخمین Q-value‌ها افزایش یافت، مقدار آن کاهش پیدا کند.

توازن جست‌و‌جو و استخراج

گام ۴-۵: ارزیابی

انجام عمل a و مشاهده حالت خروجی s و پاداش r.

اکنون باید تابع (Q(s,a به روز رسانی شود. عمل a که در گام ۳ انتخاب شده بود انجام می‌شود و اجرای این عمل حالت s و پاداش r را در خروجی می‌دهد (همانطور که در فرآیند یادگیری تقویتی در قسمت اول این مطلب بیان شد). سپس، برای به روز رسانی (Q(s,a، از «معادله بلمن» (Bellman equation) استفاده می‌شود.

معادله بلمن

در اینجا، ایده به روز رسانی (Q(state, action، مانند آنچه در کد زیر بیان شده است.

New Q value = 
   Current Q value + 
   lr * [Reward + discount_rate * (highest Q value between possible actions from the new state s’ ) — Current Q value ]

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

مثالی از Q-Learning

  • یک پنیر = ۱+
  • دو پنیر = ۲+
  • کوه عظیمی از پنیر = ۱۰+ (پایان اپیزود)
  • اگر موش، سم مرگ موش را بخورد = ۱۰- (پایان اپیزود)

گام ۱: انجام مقداردهی اولیه در Q-table

Q-Table

گام ۲: انتخاب یک عمل

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

مساله موش و پنیر

جدول Q

موش یک تکه پنیر پیدا کرد (۱+) و اکنون می‌توان جدول Q-table را با آغاز از نقطه شروع و رفتن به راست، به روز رسانی کرد. این کار با استفاده از معادله بلمن انجام می‌شود.

گام‌های ۴-۵: به روز رسانی Q-function

به روز رسانی تابع Q

به روز رسانی تابع Q

  • ابتدا، تغییرات (ΔQ) در Q-value محاسبه می‌شود (آغاز، راست).
  • سپس، مقدار اولیه Q به ΔQ (آغاز، راست) که با نرخ یادگیری چند برابر شده، اضافه می‌شود.

نرخ یادگیری به عنوان راهی که یک شبکه به سرعت مقدار پیشین را برای مقدار جدید رها کرده قابل تامل است. اگر نرخ یادگیری ۱ است، تخمین جدید، Q-value جدید خواهد بود.

جدول Q به روز رسانی شده

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

پیاده‌سازی الگوریتم Q-learning

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

Q-Learning با FrozenLake

در ادامه، با بهره‌گیری از الگوریتم Q-Learning، عاملی طراحی می‌شود که بازی FrozenLake را انجام می‌دهد. در بازی مذکور، هدف رفتن از نقطه آغاز (S) به حالت هدف (G) با قدم زدن روی کاشی‌های یخ زده (F) و اجتناب از چاله‌ها (H) است. اگرچه، یخ لغزنده است و بنابراین حرکت همیشه در جهتی که کاربر تمایل دارد انجام نمی‌شود.

گام ۰: ایمپورت کردن وابستگی‌ها

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

  • Numpy برای Qtable
  • OpenAI Gym برای محیط FrozenLake
  • Random برای تولید اعداد تصادفی

In [1]:

import numpy as np
import gym
import random

گام ۱: ساخت محیط

  • در این گام، محیط FrozenLake ساخته می‌شود.
  • کتابخانه OpenAI Gym از محیط‌های زیادی تشکیل شده که می‌توان از آن‌ها برای آموزش عامل استفاده کرد.
  • در اینجا، محیط Frozen Lake برای آموزش عامل استفاده شده است.

In [2]:

env = gym.make("FrozenLake-v0")

گام ۲: ساخت Q-table و مقداردهی اولیه به آن

  • اکنون، Q-table ساخته می‌شود تا تعداد سطرها (حالت‌ها) و ستون‌های موجود (اعمال) مشخص باشد. در حال حاضر باید سایز عمل (action_size) و سایز حالت (state_size) محاسبه شود.
  • OpenAI Gym راهی برای انجام این کار فراهم می‌کند (env.action_space.n و env.observation_space.n).

In [3]:

action_size = env.action_space.n
state_size = env.observation_space.n

In [4]:

qtable = np.zeros((state_size, action_size))
print(qtable)

پیاده‌سازی Q-Learning

گام ۳: ساخت فراپارامترها

  • در ادامه فراپامترها تعیین می‌شوند.

In [5]:

total_episodes = 10000        # Total episodes
learning_rate = 0.8           # Learning rate
max_steps = 99                # Max steps per episode
gamma = 0.95                  # Discounting rate

# Exploration parameters
epsilon = 1.0                 # Exploration rate
max_epsilon = 1.0             # Exploration probability at start
min_epsilon = 0.01            # Minimum exploration probability 
decay_rate = 0.01             # Exponential decay rate for exploration prob

گام ۴: الگوریتم Q learning

  • اکنون، الگوریتم Q learning پیاده‌سازی می‌شود.

In [6]:

# List of rewards
rewards = []

# 2 For life or until learning is stopped
for episode in range(total_episodes):
    # Reset the environment
    state = env.reset()
    step = 0
    done = False
    total_rewards = 0
    
    for step in range(max_steps):
        # 3. Choose an action a in the current world state (s)
        ## First we randomize a number
        exp_exp_tradeoff = random.uniform(0, 1)
        
        ## If this number > greater than epsilon --> exploitation (taking the biggest Q value for this state)
        if exp_exp_tradeoff > epsilon:
            action = np.argmax(qtable[state,:])

        # Else doing a random choice --> exploration
        else:
            action = env.action_space.sample()

        # Take the action (a) and observe the outcome state(s') and reward (r)
        new_state, reward, done, info = env.step(action)

        # Update Q(s,a):= Q(s,a) + lr [R(s,a) + gamma * max Q(s',a') - Q(s,a)]
        # qtable[new_state,:] : all the actions we can take from new state
        qtable[state, action] = qtable[state, action] + learning_rate * (reward + gamma * np.max(qtable[new_state, :]) - qtable[state, action])
        
        total_rewards += reward
        
        # Our new state is state
        state = new_state
        
        # If done (if we're dead) : finish episode
        if done == True: 
            break
        
    episode += 1
    # Reduce epsilon (because we need less and less exploration)
    epsilon = min_epsilon + (max_epsilon - min_epsilon)*np.exp(-decay_rate*episode) 
    rewards.append(total_rewards)

print ("Score over time: " +  str(sum(rewards)/total_episodes))
print(qtable)

Python-Q-Learning

گام ۵: استفاده از Q-table برای انجام بازی FrozenLake

  • پس از ۱۰۰۰۰ اپیزود، Q-table به عنوان برگه تقلبی برای بازی FrozenLake در دسترس است.
  • با اجرای این سلول، می‌توان شاهد انجام بازی FrozenLake توسط عامل بود.

In [ ]:

env.reset()

for episode in range(5):
    state = env.reset()
    step = 0
    done = False
    print("****************************************************")
    print("EPISODE ", episode)

    for step in range(max_steps):
        env.render()
        # Take the action (index) that have the maximum expected future reward given that state
        action = np.argmax(qtable[state,:])
        
        new_state, reward, done, info = env.step(action)
        
        if done:
            break
        state = new_state
env.close()

جمع‌بندی

  • Q-learning یک الگوریتم یادگیری تقویتی ارزش محور است که برای پیدا کردن سیاست انتخاب عمل بهینه از تابع Q استفاده می‌کند.
  • این الگوریتم، عمل مناسب انجام را بر مبنای تابع عمل-ارزش (action-value) ارزیابی می‌کند که ارزش قرار گرفتن در حالت قطعی و انجام یک عمل مشخص در آن حالت را به دست می‌دهد.
  • هدف این الگوریتم بیشینه‌سازی تابع ارزش Q است (پاداش آینده مورد انتظار با توجه به یک حالت و عمل داده شده)
  • جدول Q به عامل در پیدا کردن بهترین عمل برای حالت کمک می‌کند.
  • بیشینه‌سازی پاداش مورد انتظار با انتخاب همه بهترین اعمال ممکن انجام می‌شود.
  • Q سرنامی برای «quality» یک عمل مشخص در یک حالت مشخص است.
  • تابع (Q(state, action، پاداش آینده مورد انتظار برای یک عمل در حالت تعیین شده را باز می‌گرداند.
  • این تابع با استفاده از Q-learning قابل تخمین زدن است و به طور تکرار شونده (Q(s,a را با استفاده از معادله بلمن به روز رسانی می‌کند.
  • پیش از آنکه محیط جست‌و‌جو شود، جدول Q مقادیر ثابت دلخواه را به دست می‌دهد‌، اما با آغاز جست‌و‌جوی عامل در محیط، Q تخمین‌های بهتر و بهتری را ارائه می‌کند.

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

اگر نوشته بالا برای شما مفید بوده، آموزش‌های زیر نیز به شما پیشنهاد می‌شود:

^^

بر اساس رای ۳۱ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
Medium

نظر شما چیست؟

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