راهزن چند دست

ردیفی از ماشین‌های بازی در لاس وگاس

در تئوری احتمالات و یادگیری ماشین ، مسئله راهزن چند دست مسئله‌ای است که در آن مجموعه محدود ثابتی از منابع باید بین گزینه‌های رقیب تخصیص داده شود. انتخاب‌ها به گونه‌ای که سود مورد انتظار آنها را به حداکثر برساند، زمانی که ویژگی‌های هر انتخاب در زمان تخصیص فقط تا حدی شناخته شده است و ممکن است با گذشت زمان یا با تخصیص منابع به آن انتخاب، بهتر شناخته شود. </ref> این یک مسئله کلاسیک یادگیری تقویتی است که مسئله معاوضه اکتشاف – بهره برداری را توصیف می‌زند. این نام از تصور یک قمارباز در ردیف دستگاه‌های بازی گرفته شده است، که باید تصمیم بگیرد که با کدام دستگاه‌ها بازی کند، هر دستگاه را چند مرتبه بازی کند و به چه ترتیبی بازی کند، و آیا با دستگاه فعلی ادامه دهد یا دستگاه دیگری را امتحان کند. مسئله راهزن چند دست در دسته‌بندی برنامه‌ریزی تصادفی قرار می‌گیرد.

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

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

انگیزه تجربی

چگونه باید بودجه معینی بین این بخش‌های تحقیقاتی توزیع شود تا نتایج به حداکثر برسد؟

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

• کارآزمایی‌های بالینی که اثرات درمان‌های تجربی مختلف را در عین به حداقل رساندن تلفات بیمار بررسی می‌کنند،
• تلاش‌های مسیریابی تطبیقی برای به حداقل رساندن تاخیر در شبکه،
• طراحی سبد مالی

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

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

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

نسخه‌ای از مسئله که اکنون معمولاً مورد بررسی قرار می‌گیرد توسط هربرت رابینز در سال 1952 فرموله شده است.

مدل راهزن چند دستی

راهزن چند دستی (کوتاه: MAB) را می‌توان به عنوان مجموعه ای از توزیع‌های واقعی دید. $B=\{R_1,\dots ,R_K\}$ ، هر توزیع با پاداش‌های ارائه شده توسط یکی از $K\in {\mathbb{N}}^{+}$ اهرم مرتبط است. اگر ${\mu }_1,\dots ,{\mu }_K$ مقادیر میانگین مرتبط با این توزیع‌های پاداش باشد، قمارباز به طور مکرر در هر دور یک اهرم بازی می‌کند و پاداش مربوطه را مشاهده می‌کند. هدف این است که مجموع پاداش‌های جمع آوری شده را به حداکثر برساند. افق $H$ تعداد دورهایی است که باید انجام شود. مسئله راهزن به طور رسمی معادل فرآیند تصمیم گیری مارکوف یک حالته است. پشیمانی $\rho$ بعد از $T$ دور به عنوان تفاوت مورد انتظار بین مجموع پاداش مرتبط با یک استراتژی بهینه و مجموع پاداش‌های جمع آوری شده تعریف می‌شود:

$\rho =T{\mu }^{*}-\sum _{t=1}^T{\hat{r}}_t$ ،

جایی که ${\mu }^{*}$ حداکثر میانگین پاداش است، ${\mu }^{*}=\underset{k}{\max }\{{\mu }_k\}$ ، و ${\hat{r}}_t$ پاداش در دور t است.

استراتژی صفر پشیمانی استراتژی است که میانگین پشیمانی آن در هر راند $\rho /T$ وقتی تعداد دورهای بازی شده به بی نهایت میل می‌کند با احتمال 1 به صفر میل می‌کند. به طور شهودی، استراتژی‌های بدون پشیمانی تضمین می‌شوند که اگر راندهای کافی بازی شوند، به یک استراتژی بهینه (الزاماً منحصربه‌فرد) همگرا می‌شوند.

تغییرات

یک فرمول متداول، راهزن چند دست دودویی یا راهزن چند دست برنولی است که یک جایزه با احتمال $p$ صادر می‌کند و در غیر این صورت پاداش صفر است.

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

محققان علوم کامپیوتر راهزنان چند دست را تحت بدترین مفروضات (worst-case) مورد مطالعه قرار داده‌اند و الگوریتم‌هایی را برای به حداقل رساندن پشیمانی در زمانی متناهی و نامتناهی برای بازدهی اهرم‌های تصادفی و غیر تصادفی به دست آورده‌اند.

استراتژی‌های راهزن

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

راه حل‌های بهینه

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

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

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

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

• UCBC (محدوده‌های بالای اطمینان تاریخی با خوشه‌ها): الگوریتم UCB را برای یک تنظیم جدید به گونه ای تطبیق می‌دهد که بتواند هم خوشه بندی و هم اطلاعات تاریخی را در خود جای دهد. این الگوریتم مشاهدات تاریخی را با استفاده از هر دو در محاسبه پاداش میانگین مشاهده شده و عبارت عدم قطعیت ترکیب می‌کند. این الگوریتم اطلاعات خوشه‌بندی را با بازی در دو سطح ترکیب می‌کند: ابتدا انتخاب یک خوشه با استفاده از یک استراتژی شبیه به UCB در هر مرحله زمانی، و متعاقبا انتخاب یک اهرم از درون خوشه، دوباره با استفاده از یک استراتژی مشابه UCB.

راه حل‌های تقریبی

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

استراتژی‌های نیمه یکنواخت

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

• استراتژی اپسیلون حریص : بهترین اهرم برای نسبت $1-ϵ$ از آزمایش‌ها انتخاب می‌شود، و یک اهرم به طور تصادفی (با احتمال یکنواخت) برای یک نسبت $ϵ$ انتخاب می‌شود. یک مقدار پارامتر متداول ممکن است $ϵ=0.1$ باشد، اما بسته به شرایط و تمایلات می‌تواند بسیار متفاوت باشد.
• استراتژی اپسیلون اولالگو:مدرک : مرحله اکتشاف خالص با مرحله بهره برداری خالص دنبال می‌شود. برای $N$ آزمایش در مجموع، مرحله اکتشاف $ϵN$ آزمایش‌ها را اشغال می‌کند و مرحله بهره برداری $(1-ϵ)N$ آزمایش. در طول مرحله اکتشاف، یک اهرم به طور تصادفی انتخاب می‌شود (با احتمال یکنواخت). در طول مرحله بهره برداری، بهترین اهرم همیشه انتخاب می‌شود.
• استراتژی کاهش اپسیلونالگو:مدرک : شبیه به استراتژی epsilon-greedy، با این تفاوت که ارزش $ϵ$ با پیشرفت آزمایش کاهش‌ می‌یابد و در نتیجه رفتار بسیار اکتشافی در شروع و رفتار بسیار استثمارگرانه در پایان ایجاد می‌شود.
• استراتژی تطبیقی حریصانه-اپسیلون بر اساس تفاوت‌های ارزشی (VDBE) : مشابه استراتژی کاهش اپسیلون است، با این تفاوت که اپسیلون بر اساس پیشرفت یادگیری به جای تنظیم دستی کاهش می‌یابد (Tokic، 2010). نوسانات زیاد در برآورد ارزش، منجر به اپسیلون بالا (اکتشاف زیاد، بهره برداری کم) می‌شود. نوسانات کم به یک اپسیلون کم (اکتشاف کم، بهره برداری زیاد) منجر می‌شود. بهبودهای بیشتر را می‌توان با انتخاب کنش با وزن نرم افزار در مورد اقدامات اکتشافی به دست آورد ( Tokic & Palm, 2011).
• استراتژی تطبیقی epsilon-greedy مبتنی بر گروه‌های بیزی (Epsilon-BMC) : یک استراتژی انطباق اپسیلون تطبیقی برای یادگیری تقویتی مشابه VBDE، با تضمین‌های همگرایی یکنواخت است. در این چارچوب، پارامتر اپسیلون به‌عنوان انتظار توزیع پسینی در نظر گرفته می‌شود که وزن یک عامل حریص (که کاملاً به پاداش آموخته‌ شده اعتماد دارد) و عامل یادگیری یکنواخت (که به پاداش آموخته‌ شده بی‌اعتماد است) دارد. این توزیع پسین با استفاده از یک توزیع بتا مناسب با فرض نرمال بودن پاداش‌های مشاهده شده تقریب زده می‌شود. به منظور پرداختن به خطر احتمالی کاهش سریع اپسیلون، عدم قطعیت در واریانس پاداش آموخته شده نیز با استفاده از یک مدل گامای نرمال مدل‌سازی و به‌روزرسانی می‌شود. (گیملفارب و همکاران، 2019).
• استراتژی متنی-اپسیلون-حریصانه: مشابه استراتژی اپسیلون-حریصانه، با این تفاوت که ارزش $ϵ$ با توجه به وضعیت در فرآیندهای آزمایشی محاسبه می‌شود، که به الگوریتم اجازه می‌دهد Context-Aware باشد. این مبتنی بر اکتشاف/استثمار پویا است و می‌تواند با تصمیم‌گیری اینکه کدام موقعیت برای اکتشاف یا بهره‌برداری مناسب‌تر است، به طور انطباقی بین دو جنبه تعادل برقرار کند، که منجر به رفتار بسیار اکتشافی زمانی که موقعیت بحرانی نیست و رفتار بسیار استثمارگرانه در موقعیت بحرانی می‌شود.

استراتژی‌های تطبیق احتمال

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

استراتژی‌های قیمت گذاری

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

راهزن زمینه‌ای

یک تعمیم مفید از راهزن چند دست، راهزن چند دست زمینه‌ای است. در هر تکرار، یک عامل هنوز باید بین اهرم‌ها انتخاب کند، اما همچنین یک بردار ویژگی d بعدی را می‌بیند، بردار زمینه ای که می‌تواند همراه با پاداش اهرم‌های بازی شده در گذشته برای انتخاب اهرم بازی استفاده کند. با گذشت زمان، هدف یادگیرنده جمع‌آوری اطلاعات کافی در مورد چگونگی ارتباط بردارهای زمینه و پاداش‌ها با یکدیگر است، به طوری که بتواند بهترین اهرم بعدی را با نگاه کردن به بردارهای ویژگی پیش‌بینی کند.

راه حل‌های تقریبی برای راهزن زمینه‌ای

استراتژی‌های زیادی وجود دارند که راه‌حلی تقریبی برای مسئله راهزن زمینه‌ای ارائه می‌دهند و می‌توان آن‌ها را در دو دسته کلی به تفصیل در زیر قرار داد.

راهزنان خطی آنلاین

• الگوریتم LinUCB (محدوده اطمینان بالا) : نویسندگان یک وابستگی خطی بین پاداش مورد انتظار یک عمل و زمینه آن فرض می‌کنند و فضای نمایش را با استفاده از مجموعه‌ای از پیش‌بینی‌کننده‌های خطی مدل می‌کنند.
• الگوریتم LinRel (یادگیری تقویتی انجمنی خطی) : شبیه LinUCB است، اما از تجزیه ارزش تکی به جای رگرسیون Ridge برای به دست آوردن تخمینی از اطمینان استفاده می‌کند.
• HLINUCBC (LINUCB تاریخی با خوشه‌ها) : پیشنهاد شده در مقاله، ایده LinUCB را با اطلاعات تاریخی و خوشه‌بندی گسترش می‌دهد.

راهزنان غیر خطی آنلاین

• الگوریتم UCBogram : توابع پاداش غیرخطی با استفاده از یک برآوردگر ثابت تکه ای به نام رگرسیون در رگرسیون ناپارامتریک تخمین زده می‌شوند. سپس، UCB روی هر قطعه ثابت استفاده می‌شود. اصلاحات متوالی پارتیشن فضای زمینه به صورت تطبیقی برنامه ریزی یا انتخاب می‌شوند.
• الگوریتم‌های خطی تعمیم‌یافته : توزیع پاداش از یک مدل خطی تعمیم‌یافته پیروی می‌کند، توسعه‌ای برای راهزن‌های خطی.
• الگوریتم NeuralBandit : در این الگوریتم چندین شبکه عصبی برای مدل‌سازی ارزش پاداش‌ها با دانستن زمینه آموزش داده می‌شوند و از یک رویکرد چند متخصص برای انتخاب آنلاین پارامترهای پرسپترون‌های چند لایه استفاده می‌کنند.
• الگوریتم KernelUCB : یک نسخه غیرخطی هسته‌ای از linearUCB، با پیاده‌سازی کارآمد و تحلیل زمان محدود.
• الگوریتم جنگل راهزن : یک جنگل تصادفی با دانستن توزیع مشترک زمینه‌ها و پاداش‌ها در جنگل تصادفی ساخته شده و تحلیل می‌شود.
• الگوریتم مبتنی بر اوراکل : این الگوریتم مسئله راهزن زمینه ای را به یک سری مسائل یادگیری نظارت شده کاهش می‌دهد و بر فرض تحقق پذیری معمولی در تابع پاداش متکی نیست.

راهزن زمینه‌ای محدود

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

در عمل، معمولاً هزینه ای مرتبط با منابع مصرف شده توسط هر اقدام وجود دارد و هزینه کل توسط بودجه در بسیاری از کاربردها مانند جمع سپاری و آزمایش‌های بالینی محدود می‌شود. راهزن زمینه‌ای محدود (CCB) چنین مدلی است که هم محدودیت‌های زمانی و هم بودجه را در یک محیط راهزن چند دست در نظر می‌گیرد. A. Badanidiyuru و همکاران. ابتدا راهزن‌های زمینه‌ای را با محدودیت‌های بودجه مورد مطالعه قرار داد، که به آنها راهزن‌های زمینه‌ای منبع نیز می‌گویند و نشان داد که $O(\sqrt{T})$ پشیمانی دست یافتنی است با این حال، کار آنها بر روی مجموعه محدودی از سیاست‌ها متمرکز است و الگوریتم از نظر محاسباتی ناکارآمد است.

چارچوب UCB-ALP برای راهزنان زمینه‌ای محدود

یک الگوریتم ساده با پشیمانی لگاریتمی در موارد زیر پیشنهاد شده است:

جستارهای وابسته

• شاخص گیتینز - یک استراتژی قدرتمند و کلی برای بررسی مسئله راهزن.
• الگوریتم حریص
• توقف بهینه
• نظریه جستجو
• برنامه ریزی تصادفی