مقدمه ای بر راهزنان چند مسلح

مشاهده در TensorFlow.org در Google Colab اجرا شود مشاهده منبع در GitHub دانلود دفترچه یادداشت

معرفی

Multi-Armed Bandit (MAB) یک چارچوب یادگیری ماشینی است که در آن یک عامل باید اقدامات (بازوها) را برای به حداکثر رساندن پاداش تجمعی خود در طولانی مدت انتخاب کند. در هر دور، عامل اطلاعاتی در مورد وضعیت فعلی (زمینه) دریافت می کند، سپس اقدامی را بر اساس این اطلاعات و تجربه جمع آوری شده در دورهای قبلی انتخاب می کند. در پایان هر دور، نماینده پاداش مربوط به اقدام انتخاب شده را دریافت می کند.

شاید خالص ترین نمونه از این مسائل که نام خود را به MAB قرض است: تصور کنید که ما با آن مواجه k دستگاه های حافظه (راهزنان مسلح)، و ما به شکل نیاز کردن که یکی از بهترین پرداخت، در حالی که بیش از حد پول از دست دادن ندارد.

راهزنان چند مسلح

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

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

راهزنان چند مسلح و آموزش تقویتی

چرا یک مجموعه MAB در کتابخانه TF-Agents وجود دارد؟ ارتباط بین RL و MAB چیست؟ راهزنان چند مسلح را می توان به عنوان یک مورد خاص از یادگیری تقویتی در نظر گرفت. به قول معرفی به RL :

در هر مرحله زمان، عامل طول می کشد یک عمل بر محیط زیست بر اساس سیاست خود \(\pi(a_t|s_t)\)، که در آن \(s_t\) مشاهده در حال حاضر از محیط زیست است، و دریافت پاداش \(r_{t+1}\) و مشاهدات بعدی \(s_{t+1}\) از محیط . هدف بهبود خط مشی است تا مجموع پاداش ها (بازده) به حداکثر برسد.

در مورد RL طور کلی، مشاهدات بعدی \(s_{t+1}\) بستگی به حالت قبلی \(s_t\) و عمل \(a_t\) گرفته شده توسط سیاست. این قسمت آخر چیزی است که MAB را از RL جدا می کند: در MAB، وضعیت بعدی که مشاهده است، به عمل انتخاب شده توسط عامل بستگی ندارد.

این شباهت به ما اجازه می دهد تا از تمام مفاهیم موجود در TF-Agents استفاده مجدد کنیم.

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

محیط قارچ

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

قارچ

مجموعه داده قارچ، درست مانند همه مجموعه داده های یادگیری تحت نظارت، می تواند به یک مشکل MAB متنی تبدیل شود. ما با استفاده از روش نیز استفاده ریکلمه و همکاران (2018) . در این تبدیل، عامل ویژگی های یک قارچ را دریافت می کند، تصمیم می گیرد آن را بخورد یا نه. خوردن یک قارچ خوراکی باعث پاداش +5 می شود، در حالی که خوردن یک قارچ سمی با احتمال مساوی 5+ یا 35- می دهد. نخوردن قارچ مستقل از نوع قارچ 0 پاداش دارد. جدول زیر به طور خلاصه تکالیف پاداش را نشان می دهد:

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

نماینده LinUCB

عملکرد خوب در یک محیط راهزن متنی مستلزم برآورد خوبی از عملکرد پاداش هر عمل، با توجه به مشاهده است. یک امکان تخمین تابع پاداش با توابع خطی است. است که، برای هر عمل \(i\)، ما در حال تلاش برای پیدا کردن پارامتر \(\theta_i\in\mathbb R^d\) که برآورد

\(r_{t, i} \sim \langle v_t, \theta_i\rangle\)

تا حد امکان به واقعیت نزدیک هستند. در اینجا \(v_t\in\mathbb R^d\) زمینه دریافت در زمان مرحله است \(t\). سپس، در صورتی که عامل اعتماد به نفس در برآورد آن، آن را می توانید انتخاب کنید \(\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle\) برای گرفتن بالاترین پاداش انتظار می رود.

همانطور که در بالا توضیح داده شد، صرفاً انتخاب بازویی با بهترین پاداش تخمینی به یک استراتژی خوب منجر نمی شود. هستند بسیاری از راه های مختلف به مخلوط بهره برداری و اکتشاف در عوامل برآوردگر خطی، و یکی از مهمترین و معروف اطمینان خطی کران بالا (LinUCB) الگوریتم است (برای مثال لی و همکاران 2010 ). LinUCB دو بلوک اصلی دارد (با برخی از جزئیات حذف شده است):

  1. آن را حفظ تخمین می زند برای پارامترهای هر بازو با خطی حداقل مربعات: \(\hat\theta_i\sim X^+_i r_i\)، که در آن \(X_i\) و \(r_i\) زمینه انباشته و پاداش های دور که در آن بازو هستند \(i\) انتخاب شد، و \(()^+\) معکوس شبه است .
  2. آن را حفظ بیضی اعتماد به نفس تعریف شده توسط معکوس کوواریانس \(X_i^\top X_i\) برای برآورد کنید.

ایده اصلی LinUCB "خوش بینی در مواجهه با عدم قطعیت" است. عامل اکتشاف را از طریق افزایش برآوردها با مقداری که با واریانس آن تخمین ها مطابقت دارد، ترکیب می کند. این جایی است که بیضی اعتماد به نفس را به تصویر آمده: برای هر بازو، برآورد خوش بینانه است \(\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle\)، که در آن \(E_i\) در اطراف بیضی است \(\hat\theta_i\). انتخاب نمونه بهترین عامل به دنبال بازوی \(\arg\max_i\hat r_i\).

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

بعد چه می شود؟

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