کاوش یا بهره‌برداری

دوراهی

فرض کنید یه رستوران نزدیک خونه‌تون هست که می‌دونید غذاش خوبه. امشب چی کار می‌کنید؟

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

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

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

چند گزینه

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

گزینه‌ی یک رو ۸ بار امتحان کردیم و میانگینش حدود ۶ بوده؛ تقریبا مطمئنیم همینه. گزینه‌ی دو رو فقط ۳ بار امتحان کردیم و ۵ دیدیم؛ ولی ۳ بار کمه، شاید بدشانس بودیم. گزینه‌ی سه یه بار، و گزینه‌ی چهار هیچ‌وقت.

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

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

پشیمانی

چطوری بفهمیم یه راهبرد برای کاوش خوبه یا بد؟ با یه عدد که اسمش خیلی قشنگه:

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

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

اپسیلون

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

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

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

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

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

سه رستوران با پایتون

بیایید همون دوراهی رستوران رو با کد ببینیم. سه تا رستوران داریم؛ یه رستوران از هر ۱۰ شب ۳ شب غذاش خوبه، یکی ۵ شب، یکی ۷ شب. این عددها ساختگی‌ان و عامل خبر نداره. هزار شب، هر شب یه جا می‌ره و اگه شب خوبی بود یه امتیاز می‌گیره. یه بار همیشه بهترین فعلی رو برمی‌داره، یه بار ۱۰ درصد شب‌ها شانسی می‌ره. هر کدوم رو ۵۰۰ بار تکرار کردیم:

import random
random.seed(3)
chance = [0.3, 0.5, 0.7]          # شانس خوب بودن هر رستوران؛ عامل خبر نداره

def play(eps, days=1000):
    total = [0, 0, 0]              # جمع امتیاز هر رستوران
    count = [0, 0, 0]              # چند بار رفتیم
    score = 0
    for day in range(days):
        if day < 3:
            a = day                # هر کدوم یه بار
        elif random.random() < eps:
            a = random.randrange(3)
        else:
            a = max(range(3), key=lambda i: total[i] / count[i])
        r = 1 if random.random() < chance[a] else 0
        total[a] += r; count[a] += 1; score += r
    return score, count

for eps in (0.0, 0.1):
    runs = [play(eps) for _ in range(500)]
    avg = sum(s for s, c in runs) / 500
    stuck = sum(1 for s, c in runs if c[2] < 500) / 5
    print("eps", eps, "avg score", round(avg), "stuck on a worse one", stuck, "%")

eps 0.0 avg score 601 stuck on a worse one 35.4 %
eps 0.1 avg score 667 stuck on a worse one 2.6 %

اگه از روز اول می‌دونستیم رستوران سوم بهترینه، توی هزار شب حدود ۷۰۰ امتیاز می‌گرفتیم. عاملی که همیشه بهترین فعلی رو برداشت، میانگین ۶۰۱ گرفت؛ و توی ۳۵ درصد از بارها، روی یه رستوران بدتر گیر کرد. چرا؟ چون شب اول که رستوران سوم رو امتحان کرد، شاید بدشانسی آورد و صفر گرفت، و از اون به بعد دیگه هیچ‌وقت سراغش نرفت. عاملی که ۱۰ درصد شب‌ها شانسی رفت، میانگین ۶۶۷ گرفت و فقط ۲٫۶ درصد گیر کرد. یعنی کمی گشتن، با اینکه هر بار یه شب رو خراب می‌کنه، کل حساب رو بهتر کرد.

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

جایزه‌ی کاوش

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

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

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

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

جایزه با فرمول

اون جایزه‌ی ندونستن یه فرمول معروف داره که پیتر اوئر، نیکولو چزا بیانکی و پاول فیشر سال ۲۰۰۲ دادن. به انگلیسی بهش می‌گن UCB، کوتاه‌شده‌ی Upper Confidence Bound، یعنی «سقف اطمینان». به زبان ساده: برای هر گزینه، میانگینی که دیدیم رو برمی‌داریم و یه جایزه بهش اضافه می‌کنیم؛ جایزه‌ای که هر چی کل بازی جلوتر بره کمی بزرگ‌تر می‌شه، و هر چی خود اون گزینه بیشتر امتحان بشه، کوچیک‌تر. دقیق‌ترش اینه: جایزه برابره با جذر «لگاریتم تعداد کل دورها تقسیم بر تعداد دفعه‌هایی که این گزینه امتحان شده»، ضرب در یه عدد که خودمون تنظیم می‌کنیم.

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

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

پنج روش کنار هم

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

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

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

نمونه‌گیری تامسون

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

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

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

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

تامسون با شمردن

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

کد کامل تامسون توی آزمایش آگهی‌ها فقط یه خط بود: از منحنی هر آگهی، با همون دو عدد برد و باخت، یه عدد شانسی بکش و بزرگ‌ترین رو نشون بده. بعد از هر نمایش، یکی به برد یا باخت همون آگهی اضافه کن. نه ε لازمه، نه تنظیم جایزه. برای همین هم امروز توی سیستم‌های آگهی و پیشنهاد خیلی پرکاربرده. جالبه که این ایده رو ویلیام تامسون سال ۱۹۳۳ داده بود، ولی تا سال ۲۰۱۱، که الیویه شاپل و لیهونگ لی نشون دادن توی کار واقعی چقدر خوبه، کمتر کسی جدی‌ش گرفته بود.

آزمایش A/B یا این روش‌ها؟

یه جای خیلی رایج این دوراهی، سایت‌هاست. مثلا فرض کنید سه تا آگهی دارید و نمی‌دونید کدوم بیشتر کلیک می‌خوره. راه قدیمی اسمش آزمایش A/B هست: یه مدت هر آگهی رو به یه اندازه نشون می‌دید، بعد بهترین رو انتخاب می‌کنید و از اون به بعد فقط اون رو. ما سه تا آگهی ساختگی با نرخ کلیک ۴، ۵ و ۶ درصد گذاشتیم، ۱۰ هزار نمایش، و هر روش رو هزار بار امتحان کردیم:

اگه از اول می‌دونستیم آگهی سوم بهترینه، ۶۰۰ کلیک می‌گرفتیم. آزمایش A/B، که ۶ هزار نمایش اول رو برابر پخش کرد، ۵۳۷ گرفت؛ چون توی اون ۶ هزار نمایش، دو سومش رو به آگهی‌های بدتر داد. تاس ۰٫۱ به ۵۶۱ رسید، و تامسون به ۵۶۸، با ۷۵ درصد نمایش‌ها روی بهترین آگهی.

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

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

وقتی بهترین گزینه به آدمش بستگی داره

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

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

دام‌ها

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

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

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

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

کجاها و چند نکته

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

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

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

رایج‌ترینش قضاوت از روی یکی دو بار امتحانه؛ رستورانی که یه شب بد داشته، شاید بهترین باشه. بعدی تاسی که هیچ‌وقت کوچیک نمی‌شه؛ تا آخر بازی ۱۰ درصد وقت‌ها شانسی رفتن، یعنی پشیمانی که همیشه بالا می‌ره. بعدی تنظیم نکردن جایزه با اندازه‌ی مسئله، که توی آزمایش آگهی‌ها دیدیم. بعدی فراموش کردن اینکه دنیا عوض می‌شه؛ آگهی‌ای که ماه پیش بهترین بود، شاید الان نباشه، پس کاوش هیچ‌وقت نباید کامل صفر بشه. و آخری، تموم کردن زودهنگام آزمایش A/B، فقط چون یکی چند روز جلو افتاده.

از کجا اومد

این دوراهی خیلی قدیمی‌تر از یادگیری ماشینه:

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

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