سیاست و ارزش

سیاست

توی درس یادگیری تقویتی یه موش داشتیم توی هزارتو، که با رفت و برگشت یاد می‌گرفت از کجا بره. اون قاعده‌ای که آخرش یاد می‌گیره، یعنی «توی هر خونه چی کار کنم»، اسمش سیاست هست. سیاست دو جور می‌تونه باشه:

سیاست قطعی برای هر حالت دقیقا یه کار داره. مثل یه برگه که روش نوشته «خونه‌ی ۷: چپ، خونه‌ی ۸: بالا». هر بار موش به خونه‌ی ۷ برسه، همیشه می‌ره چپ.

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

خب سیاست خوب چیه؟ سیاستی که جمع پاداش‌ها رو بیشتر کنه. برای اینکه بشه سیاست‌ها رو با هم مقایسه کرد، اول باید یه عدد داشته باشیم که بگه «جمع پاداش‌ها» دقیقا یعنی چی.

بازده

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

به جمع همه‌ی پاداش‌هایی که از یه نقطه به بعد می‌رسه، می‌گن بازده. ولی یادتونه که پاداش دیرتر یه کم کمتر حساب می‌شه؟ برای همین هر پاداش رو به اندازه‌ی فاصله‌ش در ضریب تخفیف ضرب می‌کنیم. این‌جا ضریب ۰٫۹ هست و پنیر سه قدم بعد از قدم اول می‌رسه، پس ۱۰ سه بار در ۰٫۹ ضرب می‌شه و می‌شه ۷٫۲۹. بازده از قدم اول، ۷٫۲۹ هست.

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

ارزش حالت

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

به این عدد می‌گن ارزش اون حالت. خیلی ساده یعنی «بودن توی این خونه چقدر خوبه». خونه‌ی کنار پنیر ۱۰ می‌ارزه، چون یه قدم دیگه پنیره. یه خونه دورتر ۹، بعدی ۸٫۱، و همین‌جوری هر قدم دورتر، ۰٫۹ برابر قبلی. خونه‌ای که موش از اون‌جا شروع می‌کرد، پایین سمت راست، حدود ۵٫۳ می‌ارزه.

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

یه نکته‌ی مهم: ارزش همیشه به سیاست بستگی داره. این عددها مال یه موشیه که بهترین راه رو می‌ره. اگه موش ما هنوز شانسی راه بره، ارزش همین خونه‌ها خیلی کمتره، چون ممکنه کلی وقت بچرخه یا بخوره به تله. پس وقتی می‌گیم ارزش، همیشه یعنی «ارزش با این سیاست». به سیاستی که از هر خونه‌ای بهترین بازده رو بده، می‌گن سیاست بهینه.

ضریب تخفیف چقدر باشه؟

همون راهروی ۶ خونه‌ای و همون موش خوب رو با سه تا ضریب تخفیف حساب کردیم. با ضریب ۰٫۵، خونه‌ی کنار پنیر ۱۰ می‌ارزه، قبلیش ۵، بعد ۲٫۵، بعد ۱٫۲۵، و خونه‌ی اول فقط ۰٫۳۱. با ضریب ۰٫۹، خونه‌ی اول ۵٫۹. با ضریب ۰٫۹۹، خونه‌ی اول ۹٫۵۱؛ تقریبا هم‌اندازه‌ی خونه‌ی کنار پنیر.

یعنی ضریب کم، موش رو کوته‌بین می‌کنه: از پنج قدم اون‌طرف‌تر، پنیر براش تقریبا هیچی نیست، و اگه سر راه یه خرده‌نون باشه، همون رو ترجیح می‌ده. ضریب خیلی نزدیک به یک، موش رو آینده‌نگر می‌کنه، ولی یه مشکل داره: فرق خونه‌ها کم می‌شه، ۹٫۵۱ و ۹٫۶۱، و تشخیص اینکه کدوم قدم واقعا بهتره سخت‌تر می‌شه، و یادگیری هم معمولا آروم‌تر. برای همین توی خیلی از کارها عددی بین ۰٫۹ و ۰٫۹۹ انتخاب می‌کنن. یه حساب سرانگشتی هم هست: با ضریب ۰٫۹، موش تقریبا تا ۱۰ قدم جلوتر رو جدی می‌گیره؛ با ۰٫۹۹ تا ۱۰۰ قدم. چون ۱ تقسیم بر «یک منهای ضریب» تقریبا افق نگاه موش رو می‌ده.

با سیاست بد، با سیاست خوب

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

برای موش خوب، خونه‌ی کنار پنیر ۱۰ می‌ارزه و خونه‌ی اول ۵٫۹. برای موش شانسی، همون خونه‌ی کنار پنیر ۶٫۹۹ و خونه‌ی اول فقط ۱٫۰۹؛ کمتر از یک‌پنجم. خونه‌ها عوض نشدن، پنیر عوض نشد؛ فقط رفتار موش عوض شد. برای همین وقتی می‌گیم «این حالت فلان‌قدر می‌ارزه»، همیشه یه سیاست پشتشه.

ارزش کنش

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

به این عدد می‌گن ارزش کنش؛ ارزش «این حالت و این کار» با هم. توی این خونه رفتن به چپ ۸٫۱ می‌ارزه، رفتن به راست یا پایین ۶٫۶، و رفتن بالا یعنی افتادن توی تله.

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

ارزش حالت یا ارزش کنش؟

شاید بپرسید وقتی ارزش هر حالت رو داریم، چرا ارزش کنش هم لازمه. جوابش اینه که با ارزش حالت تنها، برای انتخاب کار، باید بدونید هر کار شما رو به کدوم حالت می‌بره؛ یعنی یه نقشه از دنیا لازم دارید. توی هزارتو این راحته، چون می‌دونیم «راست» یعنی خونه‌ی بعدی. ولی توی خیلی از مسئله‌ها، مثل یه بازی پیچیده یا یه ربات توی دنیای واقعی، این نقشه رو نداریم.

ارزش کنش این مشکل رو حل می‌کنه: موش برای هر خونه و هر کار یه عدد داره، و فقط کافیه بزرگ‌ترین رو برداره؛ بی اینکه بدونه بعدش کجا می‌ره. هزینه‌ش اینه که عددهای بیشتری باید یاد بگیره؛ اگه ۲۰ خونه و ۴ کار داریم، به‌جای ۲۰ عدد، ۸۰ عدد. برای همین روش‌هایی که نقشه ندارن، معمولا سراغ ارزش کنش می‌رن، و یادگیری Q، که درس بعده، دقیقا همینه.

ایده‌ی بلمن

خب این همه عدد رو چطوری حساب کنیم؟ یه ایده‌ی خیلی ساده هست که کل کار روش سوار می‌شه:

ارزش این خونه، یعنی همه‌ی پاداش‌هایی که از این‌جا به بعد می‌گیرم. این رو می‌شه دو تیکه کرد: پاداش همین یه قدم، و هر چی بعد از اون میاد. هر چی بعد از اون میاد، خودش ارزش خونه‌ی بعدیه! فقط چون یه قدم دیرتره، در ۰٫۹ ضربش می‌کنیم. پس اگه خونه‌ی بعد ۹ بیارزه و این قدم پاداشی نداشته باشه، این خونه ۰٫۹ ضرب در ۹، یعنی ۸٫۱ می‌ارزه.

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

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

معادله‌ی بلمن، دور به دور

حالا ببینیم معادله‌ی بلمن چطور ارزش‌ها رو پیدا می‌کنه. همه‌ی خونه‌های همون راهرو رو با صفر شروع می‌کنیم و هر دور، برای هر خونه، بهترین «پاداش این قدم به‌علاوه‌ی ۰٫۹ ضرب در ارزش خونه‌ی بعد» رو حساب می‌کنیم:

دور اول، فقط خونه‌ی کنار پنیر یه عدد گرفت، ۱۰؛ بقیه هنوز صفرن، چون هنوز خبری از پنیر بهشون نرسیده. دور دوم، خونه‌ی قبلیش ۹ شد؛ دور سوم ۸٫۱؛ و همین‌طور، هر دور یه خونه عقب‌تر. بعد از ۶ دور، همه‌ی خونه‌ها عدد درستشون رو دارن، و دور هفتم هیچ‌چیز عوض نمی‌شه؛ یعنی کار تموم. خبر پنیر، مثل یه موج، قدم به قدم از ته راهرو به اولش رسید. به این روش تکرار ارزش می‌گن.

با پایتون

همین تکرار ارزش، با پایتون خالی. خودمون اجراش کردیم:

# made up: a corridor of 6 cells; the cheese (+10) is just past the last cell; every other step pays 0
n, gamma = 6, 0.9

def sweep(V):
    new = []
    for i in range(n):
        right = 10 if i == n - 1 else gamma * V[i + 1]      # step right: cheese, or the next cell
        left = gamma * V[i - 1] if i > 0 else gamma * V[i]   # step left: the cell before (a wall at the start)
        new.append(max(right, left))                         # Bellman: the best of the two
    return new

V = [0.0] * n
for k in range(1, 8):
    V = sweep(V)
    print("sweep", k, [round(v, 2) for v in V])

sweep 1 [0.0, 0.0, 0.0, 0.0, 0.0, 10]
sweep 2 [0.0, 0.0, 0.0, 0.0, 9.0, 10]
sweep 3 [0.0, 0.0, 0.0, 8.1, 9.0, 10]
sweep 4 [0.0, 0.0, 7.29, 8.1, 9.0, 10]
sweep 5 [0.0, 6.56, 7.29, 8.1, 9.0, 10]
sweep 6 [5.9, 6.56, 7.29, 8.1, 9.0, 10]
sweep 7 [5.9, 6.56, 7.29, 8.1, 9.0, 10]

کل کار، اون یه خط max(right, left) هست: برای هر خونه، از بین کارهای ممکن، اونی که «پاداش به‌علاوه‌ی ارزش تخفیف‌خورده‌ی بعدی»ش بیشتره. این همون معادله‌ی بلمنه، توی یه خط. اگه به‌جای max، میانگین دو تا کار رو بگیریم، ارزش سیاست شانسی درمیاد؛ همون عددهای ۱٫۰۹ تا ۶٫۹۹ که بالاتر دیدیم.

پیدا کردن عددها

موش نقشه‌ی هزارتو رو نداره؛ فقط می‌تونه بازی کنه و ببینه چی می‌شه. دو راه اصلی هست که از همین تجربه، ارزش‌ها رو پیدا کنه:

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

راه دوم اینه که هر قدم یاد بگیریم. موش لازم نیست صبر کنه تا آخر؛ همین که یه قدم رفت، پاداش همین قدم رو داره و یه حدس هم از ارزش خونه‌ی بعد. با ایده‌ی بلمن، ارزش خونه‌ی قبلی رو یه کم به سمت «پاداش + ۰٫۹ × حدس خونه‌ی بعد» می‌بره. به این روش می‌گن تفاضل زمانی.

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

کدوم سریع‌تر یاد می‌گیره؟

مونت‌کارلو یا تفاضل زمانی؟ یه آزمایش کلاسیک از کتاب ریچارد ساتن و اندرو بارتو رو تکرار کردیم: یه راهروی ۵ خونه‌ای، موش از وسط شروع می‌کنه و هر قدم شانسی چپ یا راست می‌ره؛ اگه از سمت راست بیرون بره پاداش ۱، از چپ صفر. ارزش درست هر خونه رو می‌دونیم، پس می‌تونیم ببینیم هر روش چقدر بهش نزدیک می‌شه:

هر روش رو با چند نرخ یادگیری، صد بار، هر بار صد دور بازی امتحان کردیم. بهترین مونت‌کارلو بعد از ۱۰۰ دور خطای ۰٫۰۷۸ داشت؛ بهترین تفاضل زمانی ۰٫۰۳۳، کمتر از نصف. یعنی یاد گرفتن از هر قدم، با تکیه به حدس خونه‌ی بعد، اینجا سریع‌تر به جواب درست رسید. دلیلش اینه که مونت‌کارلو کل شانس یه دور رو، که می‌تونه خیلی بالا و پایین بره، توی حساب میاره؛ ولی تفاضل زمانی هر بار فقط شانس یه قدم رو. البته تفاضل زمانی هم بی‌نقص نیست؛ اگه حدس خونه‌ی بعد غلط باشه، اون غلط رو هم یه مدت با خودش می‌بره.

بهتر کردن سیاست

خب حالا که ارزش‌ها رو برای یه سیاست داریم، چطوری سیاست بهتری بسازیم؟ با یه رفت و برگشت ساده:

1. با سیاست فعلی بازی می‌کنیم و ارزش‌ها رو می‌سنجیم؛ یعنی می‌فهمیم با این سیاست، هر خونه چقدر می‌ارزه.
2. توی هر خونه، سیاست رو عوض می‌کنیم به سمت کاری که طبق همین ارزش‌ها بیشترین عدد رو داره.
3. حالا سیاست یه کم بهتر شده، پس ارزش‌ها هم عوض می‌شن. دوباره از قدم اول، تا وقتی دیگه هیچ‌کدوم عوض نشه.

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

چند دور تا بهترین؟

رونالد هاوارد سال ۱۹۶۰ این رفت و برگشت رو به شکل یه روش کامل نوشت و اسمش رو گذاشت تکرار سیاست. یه چیز جالب درباره‌ش اینه که معمولا با تعداد خیلی کمی رفت و برگشت به سیاست بهینه می‌رسه؛ چون هر بار که سیاست عوض می‌شه، دست‌کم یه جا بهتر می‌شه و هیچ‌جا بدتر نمی‌شه، و تعداد سیاست‌ها هم محدوده. توی راهروی ما، اگه از یه سیاست شانسی شروع کنیم، با یه بار سنجیدن ارزش‌ها همه‌ی خونه‌ها می‌فهمن راست بهتره؛ چون ارزش خونه‌ی سمت راست همیشه از چپ بیشتره. یعنی یه دور بهتر کردن کافیه.

راه مستقیم

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

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

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

بازیگر و منتقد

دو تا راه دیدیم: از ارزش به سیاست، و مستقیم سراغ سیاست. یه راه سوم این دو تا رو با هم داره. اندرو بارتو، ریچارد ساتن و چارلز اندرسون سال ۱۹۸۳ دو تا تیکه کنار هم گذاشتن: یه بازیگر، که خود سیاسته و تصمیم می‌گیره، و یه منتقد، که ارزش حالت‌ها رو تخمین می‌زنه. بعد از هر قدم، منتقد می‌گه «این قدم از چیزی که انتظار داشتم بهتر بود یا بدتر»، با همون حساب تفاضل زمانی؛ و بازیگر با همین نظر، اون کار رو بیشتر یا کمتر انجام می‌ده.

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

یه روش امروزی

رونالد ویلیامز سال ۱۹۹۲ یکی از اولین روش‌های گرادیان سیاست رو داد که اسمش REINFORCE شد. یکی از پرکاربردترین روش‌های امروزی PPO هست، کوتاه‌شده‌ی Proximal Policy Optimization، یعنی «بهینه‌سازی نزدیک سیاست»، از جان شولمن و همکارهاش سال ۲۰۱۷. ایده‌ی اصلیش ساده‌ست: هر قدم یادگیری، سیاست رو فقط یه کم عوض کن، نه خیلی؛ چون یه تغییر بزرگ با یه حدس پرنویز، می‌تونه سیاستی که خوب کار می‌کرد رو یهو خراب کنه.

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

چند نکته

جدول یا شبکه؟ توی هزارتوی ۲۰ خونه‌ای می‌شه برای هر خونه یه عدد نوشت؛ ولی وقتی حالت‌ها بی‌شمارن، به‌جای جدول یه شبکه‌ی عصبی می‌ذارن که ارزش حالت‌های تازه رو هم حدس بزنه. ارزش، نه پاداش: پاداش مال همین یه قدمه و ارزش، کل آینده از این‌جا به بعد؛ موش باید بر اساس ارزش تصمیم بگیره، نه پاداش، وگرنه همون داستان خرده‌نون و پنیر پیش میاد. و همه‌چی به سیاست بستگی داره: هر وقت عددی برای ارزش دیدید، بپرسید «با کدوم سیاست؟»؛ یه خونه با سیاست بد کم می‌ارزه و با سیاست خوب زیاد.

اشتباه‌های رایج

رایج‌ترینش قاطی کردن پاداش و ارزشه؛ موشی که فقط به پاداش این قدم نگاه کنه، سراغ خرده‌نون می‌ره. بعدی فراموش کردن اینکه ارزش مال یه سیاست خاصه، و مقایسه‌ی ارزش‌هایی که با سیاست‌های مختلف حساب شدن. بعدی ضریب تخفیف نامناسب؛ با ضریب خیلی کم، خبر پنیر به خونه‌های دور نمی‌رسه، چون ۰٫۵ به توان ده تقریبا صفره. و آخری عوض کردن خیلی تند سیاست با یه حدس پرنویز، که دلیل ساخته شدن روش‌هایی مثل PPO بود.

از کجا اومد

ارزش و سیاست، قدیمی‌تر از یادگیری ماشین‌ان:

ریچارد بلمن سال ۱۹۵۷ معادله‌ی خودش رو برای مسئله‌های تصمیم‌گیری پشت سر هم نوشت. رونالد هاوارد سال ۱۹۶۰ تکرار سیاست رو داد. بارتو، ساتن و اندرسون سال ۱۹۸۳ بازیگر و منتقد رو، ساتن سال ۱۹۸۸ تفاضل زمانی رو، و ویلیامز سال ۱۹۹۲ گرادیان سیاست رو. و سال ۲۰۱۷ PPO اومد که تا امروز یکی از پرکاربردترین روش‌هاست.

درس بعد یکی از معروف‌ترین راه‌های یادگیری تقویتی رو کامل می‌بینیم؛ روشی که با همین ایده‌ی بلمن، جدول ارزش کنش‌ها رو قدم به قدم پر می‌کنه: یادگیری Q.