موضوع مقاله: راهزن چند دست | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # راهزن چند دست | مقدمه: </ref> این یک مسئله کلاسیک یادگیری تقویتی است که مسئله معاوضه اکتشاف – بهره برداری را توصیف می‌زند. | ## بخش 1: راهزن چند دست | این نام از تصور یک قمارباز در ردیف دستگاه‌های بازی گرفته شده است، که باید تصمیم بگیرد که با کدام دستگاه‌ها بازی کند، هر دستگاه را چند مرتبه بازی کند و به چه ترتیبی بازی کند، و آیا با دستگاه فعلی ادامه دهد یا دستگاه دیگری را امتحان کند. در این مسئله، هر دستگاه یک پاداش تصادفی را از یک توزیع احتمال خاص برای آن دستگاه ارائه می‌کند، که این توزیع از قبل مشخص نیست. هدف قمارباز به حداکثر رساندن مجموع پاداش‌های به‌ دست‌ آمده از طریق دنباله‌ای از کشیدن اهرم‌ها است. معاوضه اساسی‌ای که قمارباز در هر آزمایشی با آن روبرو می‌شود، بین «استثمار» از دستگاهی است که بالاترین بازدهی مورد انتظار را دارد و «اکتشاف» برای به دست آوردن اطلاعات بیشتر در مورد بازدهی مورد انتظار دستگاه‌های دیگر است. در عمل، راهزن چند دست برای مدل‌سازی مسائلی مانند مدیریت پروژه‌های تحقیقاتی در یک سازمان بزرگ، مانند یک بنیاد علمی یا یک شرکت داروسازی، استفاده شده‌ است. در نسخه‌های اولیه مسئله، قمارباز بدون هیچ دانش اولیه در مورد دستگاه‌ها شروع می‌کند. هربرت رابینز در سال 1952، با درک اهمیت مسئله، استراتژی‌های انتخاب جمعیت همگرا را در "برخی از جنبه‌های طراحی متوالی آزمایش‌ها" ساخت. یک قضیه، شاخص گیتینز ، که برای اولین بار توسط جان سی منتشر شد، یک سیاست بهینه برای به حداکثر رساندن پاداش مورد انتظار ارائه می‌دهد. مسئله راهزن چند دست، عاملی را مدل می‌کند که به طور همزمان تلاش می‌کند دانش جدیدی («اکتشاف») به دست آورد و تصمیمات خود را بر اساس دانش موجود («استثمار») بهینه کند. عامل تلاش می‌کند تا این دو وظیفه رقابتی را متعادل کند تا ارزش کلی آنها را در بازه زمانی در نظر گرفته شده به حداکثر برساند. کاربردهای عملی زیادی از مسئله راهزن وجود دارد، به عنوان نمونه: کارآزمایی‌های بالینی که اثرات درمان‌های تجربی مختلف را در عین به حداقل رساندن تلفات بیمار بررسی می‌کنند، Press (1986) تلاش‌های مسیریابی تطبیقی برای به حداقل رساندن تاخیر در شبکه، طراحی سبد مالی در این مثال‌های عملی، مسئله مستلزم رسیدن به حداکثر پاداش بر اساس دانشی است که قبلاً به دست آورده‌ایم و تلاش برای اقدامات جدید برای افزایش بیشتر دانش است. این به عنوان معاوضه بهره برداری در مقابل اکتشاف در یادگیری ماشینی شناخته می‌شود. این مسئله در ابتدا توسط دانشمندان متفقین در جنگ جهانی دوم مورد توجه قرار گرفت، اما به قدری غیرقابل حل بود که به گفته پیتر ویتل ، پیشنهاد شد که این مسئله در بین آلمانی‌ها رها شود تا دانشمندان آلمانی نیز بتوانند وقت خود را برای آن تلف کنند. نسخه‌ای از مسئله که اکنون معمولاً مورد بررسی قرار می‌گیرد توسط هربرت رابینز در سال 1952 فرموله شده است. مدل راهزن چند دستی راهزن چند دستی (کوتاه: MAB) را می‌توان به عنوان مجموعه ای از توزیع‌های واقعی دید. اگر مقادیر میانگین مرتبط با این توزیع‌های پاداش باشد، قمارباز به طور مکرر در هر دور یک اهرم بازی می‌کند و پاداش مربوطه را مشاهده می‌کند. پشیمانی بعد از دور به عنوان تفاوت مورد انتظار بین مجموع پاداش مرتبط با یک استراتژی بهینه و مجموع پاداش‌های جمع آوری شده تعریف می‌شود: ، جایی که حداکثر میانگین پاداش است، ، و پاداش در دور t است. استراتژی صفر پشیمانی استراتژی است که میانگین پشیمانی آن در هر راند وقتی تعداد دورهای بازی شده به بی نهایت میل می‌کند با احتمال 1 به صفر میل می‌کند. به طور شهودی، استراتژی‌های بدون پشیمانی تضمین می‌شوند که اگر راندهای کافی بازی شوند، به یک استراتژی بهینه (الزاماً منحصربه‌فرد) همگرا می‌شوند. تغییرات یک فرمول متداول، راهزن چند دست دودویی یا راهزن چند دست برنولی است که یک جایزه با احتمال صادر می‌کند و در غیر این صورت پاداش صفر است. فرمول دیگری از راهزن چند دشت دارای هر اهرم نشان دهنده یک ماشین مارکوف مستقل است. هر بار که دستگاه خاصی بازی می‌شود، وضعیت آن دستگاه به دستگاه جدیدی می‌رود که بر اساس احتمالات تکامل حالت مارکوف انتخاب می‌شود. در یک تعمیم به نام "مسئله راهزن بی‌قرار"، حالت‌های دستگاه‌های بازی نشده نیز می تواند در طول زمان تکامل یابد. همچنین در مورد سیستم‌هایی که تعداد انتخاب‌ها (در مورد اینکه کدام دستگاه بازی شود) در طول زمان افزایش می‌یابد، بحث شده است. محققان علوم کامپیوتر راهزنان چند دست را تحت بدترین مفروضات (worst-case) مورد مطالعه قرار داده‌اند و الگوریتم‌هایی را برای به حداقل رساندن پشیمانی در زمانی متناهی و نامتناهی برای بازدهی اهرم‌های تصادفی و غیر تصادفی به دست آورده‌اند. | ## بخش 2: راهزن چند دست | استراتژی‌های راهزن یک پیشرفت بزرگ، ایجاد استراتژی‌ها یا سیاست‌های انتخاب بهینه جمعیت (که دارای حداکثر نرخ هم‌گرایی یکنواخت با جمعیت با بالاترین میانگین هستند) در کار شرح داده شده در زیر است. راه حل‌های بهینه در مقاله "قوانین تخصیص تطبیقی کارآمد مجانبی"، لای و رابینز (به دنبال مقالات رابینز و همکارانش که به رابینز در سال 1952 بازمی‌گردند) سیاست‌های انتخاب جمعیت همگرا را ارائه کردند که سریع‌ترین نرخ همگرایی را (به جمعیت با بالاترین میانگین) برای حالتی که توزیع پاداش جمعیت خانواده نمایی یک پارامتری است، دارد. سپس در کاتهاکیس و رابینز ساده‌سازی خط‌مشی و اثبات اصلی برای مورد جمعیت‌های عادی با واریانس‌های شناخته شده ارائه شد. پیشرفت قابل توجه بعدی توسط Burnetas و Katehakis در مقاله "سیاست‌های تطبیقی بهینه برای مسائل تخصیص متوالی"، به دست آمد، جایی که سیاست‌های مبتنی بر شاخص با حداکثر نرخ همگرایی یکنواخت، تحت شرایط عمومی تر که شامل مواردی است که در آن توزیع‌ها وجود دارد، ساخته شد. بعداً در «سیاست‌های تطبیقی بهینه برای فرآیندهای تصمیم مارکوف» بورنتاس و کاتهاکیس مدل بسیار بزرگ‌تری از فرآیندهای تصمیم‌گیری مارکوف را تحت اطلاعات محدود مطالعه کردند، جایی که قانون گذار و/یا پاداش‌ یک دوره ممکن است به پارامترهای ناشناخته بستگی داشته باشد. در این کار، نویسندگان یک فرم صریح برای یک کلاس از سیاست‌های تطبیقی با ویژگی‌های نرخ همگرایی حداکثری یکنواخت برای کل پاداش افق محدود مورد انتظار تحت مفروضات کافی فضاهای کنش حالت محدود و کاهش‌ناپذیری قانون گذار ارائه کردند. یکی از ویژگی‌های اصلی این سیاست‌ها این است که انتخاب اقدامات، در هر حالت و دوره زمانی، بر اساس شاخص‌هایی است که تورم‌های سمت راست معادلات میانگین تخمینی بهینه پاداش هستند. برای راهزنان چند دست برنولی، پیلارسکی و همکاران روش‌های محاسباتی استخراج راه‌حل‌های کاملاً بهینه (نه فقط مجانبی) را با استفاده از برنامه‌نویسی پویا در مقاله "سیاست بهینه برای راهزنان برنولی: محاسبات و الگوریتم" مطالعه کردند. این کار از طریق طرح‌های نمایه‌سازی، جداول جستجو و سایر تکنیک‌ها، راه‌حل‌های بهینه عملاً قابل اجرا را برای راهزنان برنولی ارائه کرد، مشروط بر اینکه افق‌های زمانی و تعداد اهرم‌ها بیش از حد بزرگ نشوند. پیلارسکی و همکاران بعداً این کار را در "پاداش تاخیری راهزنان برنولی: سیاست بهینه و متاالگوریتم پیش بینی کننده PARDI" گسترش داد تا روشی برای تعیین خط مشی بهینه راهزنان برنولی ایجاد کند، زمانی که پاداش ممکن است بلافاصله پس از یک تصمیم آشکار نشود و ممکن است به تاخیر بیفتد. این روش بر محاسبه مقادیر مورد انتظار نتایج پاداش که هنوز آشکار نشده اند و به‌روزرسانی توزیع احتمالات پسین هنگام آشکار شدن پاداش‌ها متکی است. می‌توان راه حل‌های بهینه برای راهزن چند دست برای استخراج ارزش انتخاب‌های حیوانات استفاده کرد. فعالیت نورون‌ها در آمیگدال و جسم مخطط شکمی مقادیر به دست آمده از این سیاست‌ها را رمزگذاری می‌کند و می‌تواند برای رمزگشایی زمانی که حیوانات انتخاب‌های اکتشافی در مقابل استثماری انجام دهند استفاده شود. علاوه بر این، سیاست‌های بهینه رفتار انتخاب حیوانات را بهتر از استراتژی‌های جایگزین پیش‌بینی می‌کنند (که در زیر توضیح داده شده است). این نشان می‌دهد که راه‌حل‌های بهینه برای مسئله راهزن چند دست از نظر بیولوژیکی قابل قبول هستند. UCBC (محدوده‌های بالای اطمینان تاریخی با خوشه‌ها): الگوریتم UCB را برای یک تنظیم جدید به گونه ای تطبیق می‌دهد که بتواند هم خوشه بندی و هم اطلاعات تاریخی را در خود جای دهد. این الگوریتم مشاهدات تاریخی را با استفاده از هر دو در محاسبه پاداش میانگین مشاهده شده و عبارت عدم قطعیت ترکیب می‌کند. این الگوریتم اطلاعات خوشه‌بندی را با بازی در دو سطح ترکیب می‌کند: ابتدا انتخاب یک خوشه با استفاده از یک استراتژی شبیه به UCB در هر مرحله زمانی، و متعاقبا انتخاب یک اهرم از درون خوشه، دوباره با استفاده از یک استراتژی مشابه UCB. راه حل‌های تقریبی راهبردهای زیادی وجود دارند که راه حل تقریبی برای مسئله راهزن ارائه می‌دهند و می‌توان آنها را در چهار گروه کلی که در زیر شرح داده شده است قرار داد: استراتژی‌های نیمه یکنواخت استراتژی‌های نیمه یکنواخت اولین (و ساده‌ترین) استراتژی‌هایی بودند که برای حل تقریبی مسئله راهزن کشف شدند. همه آن استراتژی‌ها رفتار حریصانه‌ای دارند که در آن بهترین اهرم (بر اساس مشاهدات قبلی) همیشه کشیده می‌شود، مگر زمانی که یک اقدام تصادفی (یکنواخت) انجام شود. بهترین اهرم برای نسبت از آزمایش‌ها انتخاب می‌شود، و یک اهرم به طور تصادفی (با احتمال یکنواخت) برای یک نسبت انتخاب می‌شود. یک مقدار پارامتر متداول ممکن است باشد، اما بسته به شرایط و تمایلات می‌تواند بسیار متفاوت باشد. استراتژی اپسیلون اول : مرحله اکتشاف خالص با مرحله بهره برداری خالص دنبال می‌شود. برای آزمایش در مجموع، مرحله اکتشاف آزمایش‌ها را اشغال می‌کند و مرحله بهره برداری آزمایش. استراتژی کاهش اپسیلون : شبیه به استراتژی epsilon-greedy، با این تفاوت که ارزش با پیشرفت آزمایش کاهش‌ می‌یابد و در نتیجه رفتار بسیار اکتشافی در شروع و رفتار بسیار استثمارگرانه در پایان ایجاد می‌شود. | ## بخش 3: راهزن چند دست | استراتژی تطبیقی حریصانه-اپسیلون بر اساس تفاوت‌های ارزشی (VDBE) : مشابه استراتژی کاهش اپسیلون است، با این تفاوت که اپسیلون بر اساس پیشرفت یادگیری به جای تنظیم دستی کاهش می‌یابد (Tokic، 2010).. نوسانات زیاد در برآورد ارزش، منجر به اپسیلون بالا (اکتشاف زیاد، بهره برداری کم) می‌شود. بهبودهای بیشتر را می‌توان با انتخاب کنش با وزن نرم افزار در مورد اقدامات اکتشافی به دست آورد ( Tokic & Palm, 2011).. در این چارچوب، پارامتر اپسیلون به‌عنوان انتظار توزیع پسینی در نظر گرفته می‌شود که وزن یک عامل حریص (که کاملاً به پاداش آموخته‌ شده اعتماد دارد) و عامل یادگیری یکنواخت (که به پاداش آموخته‌ شده بی‌اعتماد است) دارد. این توزیع پسین با استفاده از یک توزیع بتا مناسب با فرض نرمال بودن پاداش‌های مشاهده شده تقریب زده می‌شود. به منظور پرداختن به خطر احتمالی کاهش سریع اپسیلون، عدم قطعیت در واریانس پاداش آموخته شده نیز با استفاده از یک مدل گامای نرمال مدل‌سازی و به‌روزرسانی می‌شود. استراتژی متنی-اپسیلون-حریصانه: مشابه استراتژی اپسیلون-حریصانه، با این تفاوت که ارزش با توجه به وضعیت در فرآیندهای آزمایشی محاسبه می‌شود، که به الگوریتم اجازه می‌دهد Context-Aware باشد. این مبتنی بر اکتشاف/استثمار پویا است و می‌تواند با تصمیم‌گیری اینکه کدام موقعیت برای اکتشاف یا بهره‌برداری مناسب‌تر است، به طور انطباقی بین دو جنبه تعادل برقرار کند، که منجر به رفتار بسیار اکتشافی زمانی که موقعیت بحرانی نیست و رفتار بسیار استثمارگرانه در موقعیت بحرانی می‌شود. استراتژی‌های تطبیق احتمال استراتژی‌های تطبیق احتمال این ایده را منعکس می‌کند که تعداد کشیدن‌ها برای یک اهرم معین باید با احتمال واقعی آن برای بهینه بودن اهرم مطابقت داشته باشد. استراتژی‌های تطبیق احتمال نیز به‌عنوان نمونه‌گیری تامپسون یا راهزنان بیزی شناخته می‌شوند، و اگر بتوانید از توزیع پسین برای مقدار میانگین هر جایگزین نمونه برداری کنید، به‌طور شگفت‌آوری آسان می‌شوند. استراتژی‌های قیمت گذاری استراتژی‌های قیمت گذاری قیمتی را برای هر اهرم تعیین می‌کنند. به عنوان مثال، همانطور که با الگوریتم POKER نشان داده شده است، قیمت می‌تواند مجموع پاداش مورد انتظار به اضافه تخمینی از پاداش‌های اضافی آینده باشد که از طریق دانش اضافی به دست می‌آید. در هر تکرار، یک عامل هنوز باید بین اهرم‌ها انتخاب کند، اما همچنین یک بردار ویژگی d بعدی را می‌بیند، بردار زمینه ای که می‌تواند همراه با پاداش اهرم‌های بازی شده در گذشته برای انتخاب اهرم بازی استفاده کند. با گذشت زمان، هدف یادگیرنده جمع‌آوری اطلاعات کافی در مورد چگونگی ارتباط بردارهای زمینه و پاداش‌ها با یکدیگر است، به طوری که بتواند بهترین اهرم بعدی را با نگاه کردن به بردارهای ویژگی پیش‌بینی کند. راه حل‌های تقریبی برای راهزن زمینه‌ای استراتژی‌های زیادی وجود دارند که راه‌حلی تقریبی برای مسئله راهزن زمینه‌ای ارائه می‌دهند و می‌توان آن‌ها را در دو دسته کلی به تفصیل در زیر قرار داد. راهزنان خطی آنلاین الگوریتم LinUCB (محدوده اطمینان بالا) : نویسندگان یک وابستگی خطی بین پاداش مورد انتظار یک عمل و زمینه آن فرض می‌کنند و فضای نمایش را با استفاده از مجموعه‌ای از پیش‌بینی‌کننده‌های خطی مدل می‌کنند. راهزنان غیر خطی آنلاین الگوریتم UCBogram : توابع پاداش غیرخطی با استفاده از یک برآوردگر ثابت تکه ای به نام رگرسیون در رگرسیون ناپارامتریک تخمین زده می‌شوند. الگوریتم‌های خطی تعمیم‌یافته : توزیع پاداش از یک مدل خطی تعمیم‌یافته پیروی می‌کند، توسعه‌ای برای راهزن‌های خطی. الگوریتم NeuralBandit : در این الگوریتم چندین شبکه عصبی برای مدل‌سازی ارزش پاداش‌ها با دانستن زمینه آموزش داده می‌شوند و از یک رویکرد چند متخصص برای انتخاب آنلاین پارامترهای پرسپترون‌های چند لایه استفاده می‌کنند. الگوریتم جنگل راهزن : یک جنگل تصادفی با دانستن توزیع مشترک زمینه‌ها و پاداش‌ها در جنگل تصادفی ساخته شده و تحلیل می‌شود. الگوریتم مبتنی بر اوراکل : این الگوریتم مسئله راهزن زمینه ای را به یک سری مسائل یادگیری نظارت شده کاهش می‌دهد و بر فرض تحقق پذیری معمولی در تابع پاداش متکی نیست. هر تکرار این فرمول جدید ناشی از مسائل آنلاین مختلف است که در آزمایش‌های بالینی، سیستم‌های توصیه‌کننده و مدل‌سازی توجه به وجود می‌آیند. در اینجا، آنها الگوریتم راهزن استاندارد چند دستی معروف به نمونه‌برداری تامپسون را برای استفاده از تنظیمات زمینه محدود تطبیق می‌دهند و دو الگوریتم جدید به نام‌های نمونه‌برداری تامپسون با زمینه محدود (TSRC) و نمونه‌برداری تامپسون ویندوز با زمینه محدود (WTSRC) را پیشنهاد می‌کنند. راهزن زمینه‌ای محدود (CCB) چنین مدلی است که هم محدودیت‌های زمانی و هم بودجه را در یک محیط راهزن چند دست در نظر می‌گیرد. | ## جمع‌بندی | ابتدا راهزن‌های زمینه‌ای را با محدودیت‌های بودجه مورد مطالعه قرار داد، که به آنها راهزن‌های زمینه‌ای منبع نیز می‌گویند و نشان داد که پشیمانی دست یافتنی است با این حال، کار آنها بر روی مجموعه محدودی از سیاست‌ها متمرکز است و الگوریتم از نظر محاسباتی ناکارآمد است.