راهزن چند دست کیست؟ توضیح بده.
در تئوری احتمالات و یادگیری ماشین ، مسئله راهزن چند دست مسئله‌ای است که در آن مجموعه محدود ثابتی از منابع باید بین گزینه‌های رقیب تخصیص داده شود. انتخاب‌ها به گونه‌ای که سود مورد انتظار آنها را به حداکثر برساند، زمانی که ویژگی‌های هر انتخاب در زمان تخصیص فقط تا حدی شناخته شده است و ممکن است با گذشت زمان یا با تخصیص منابع به آن انتخاب، بهتر شناخته شود. &lt;/ref&gt; این یک مسئله کلاسیک یادگیری تقویتی است که مسئله معاوضه اکتشاف – بهره برداری را توصیف می‌زند. این نام از تصور یک قمارباز در ردیف دستگاه‌های بازی گرفته شده است، که باید تصمیم بگیرد که با کدام دستگاه‌ها بازی کند، هر دستگاه را چند مرتبه بازی کند و به چه ترتیبی بازی کند، و آیا با دستگاه فعلی ادامه دهد یا دستگاه دیگری را امتحان کند. مسئله راهزن چند دست در دسته‌بندی برنامه‌ریزی تصادفی قرار می‌گیرد.در این مسئله، هر دستگاه یک پاداش تصادفی را از یک توزیع احتمال خاص برای آن دستگاه ارائه می‌کند، که این توزیع از قبل مشخص نیست. هدف قمارباز به حداکثر رساندن مجموع پاداش‌های به‌ دست‌ آمده از طریق دنباله‌ای از کشیدن اهرم‌ها است. معاوضه اساسی‌ای که قمارباز در هر آزمایشی با آن روبرو می‌شود، بین «استثمار» از دستگاهی است که بالاترین بازدهی مورد انتظار را دارد و «اکتشاف» برای به دست آوردن اطلاعات بیشتر در مورد بازدهی مورد انتظار دستگاه‌های دیگر است. مبادله بین اکتشاف و بهره‌برداری در یادگیری ماشین بررسی شده است. در عمل، راهزن چند دست برای مدل‌سازی مسائلی مانند مدیریت پروژه‌های تحقیقاتی در یک سازمان بزرگ، مانند یک بنیاد علمی یا یک شرکت داروسازی، استفاده شده‌ است. در نسخه‌های اولیه مسئله، قمارباز بدون هیچ دانش اولیه در مورد دستگاه‌ها شروع می‌کند.هربرت رابینز در سال 1952، با درک اهمیت مسئله، استراتژی‌های انتخاب جمعیت همگرا را در "برخی از جنبه‌های طراحی متوالی آزمایش‌ها" ساخت. یک قضیه، شاخص گیتینز ، که برای اولین بار توسط جان سی منتشر شد، یک سیاست بهینه برای به حداکثر رساندن پاداش مورد انتظار ارائه می‌دهد.انگیزه تجربی.مسئله راهزن چند دست، عاملی را مدل می‌کند که به طور همزمان تلاش می‌کند دانش جدیدی («اکتشاف») به دست آورد و تصمیمات خود را بر اساس دانش موجود («استثمار») بهینه کند. عامل تلاش می‌کند تا این دو وظیفه رقابتی را متعادل کند تا ارزش کلی آنها را در بازه زمانی در نظر گرفته شده به حداکثر برساند. کاربردهای عملی زیادی از مسئله راهزن وجود دارد، به عنوان نمونه:در این مثال‌های عملی، مسئله مستلزم رسیدن به حداکثر پاداش بر اساس دانشی است که قبلاً به دست آورده‌ایم و تلاش برای اقدامات جدید برای افزایش بیشتر دانش است. این به عنوان "معاوضه بهره برداری در مقابل اکتشاف" در یادگیری ماشینی شناخته می‌شود.این مدل برای کنترل تخصیص پویای منابع به پروژه‌های مختلف استفاده شده است و به این سؤال پاسخ می‌دهد که با توجه به عدم اطمینان در مورد دشواری و بازدهی هر گزینه، روی کدام پروژه کار شود.این مسئله در ابتدا توسط دانشمندان متفقین در جنگ جهانی دوم مورد توجه قرار گرفت، اما به قدری غیرقابل حل بود که به گفته پیتر ویتل ، پیشنهاد شد که این مسئله در بین آلمانی‌ها رها شود تا دانشمندان آلمانی نیز بتوانند وقت خود را برای آن تلف کنند.نسخه‌ای از مسئله که اکنون معمولاً مورد بررسی قرار می‌گیرد توسط هربرت رابینز در سال 1952 فرموله شده است.مدل راهزن چند دستی.راهزن چند دستی (کوتاه: MAB) را می‌توان به عنوان مجموعه ای از توزیع‌های واقعی دید. formula_1 ، هر توزیع با پاداش‌های ارائه شده توسط یکی از formula_2 اهرم مرتبط است. اگر formula_3 مقادیر میانگین مرتبط با این توزیع‌های پاداش باشد، قمارباز به طور مکرر در هر دور یک اهرم بازی می‌کند و پاداش مربوطه را مشاهده می‌کند. هدف این است که مجموع پاداش‌های جمع آوری شده را به حداکثر برساند. افق formula_4 تعداد دورهایی است که باید انجام شود. مسئله راهزن به طور رسمی معادل فرآیند تصمیم گیری مارکوف یک حالته است. پشیمانی formula_5 بعد از formula_6 دور به عنوان تفاوت مورد انتظار بین مجموع پاداش مرتبط با یک استراتژی بهینه و مجموع پاداش‌های جمع آوری شده تعریف می‌شود:formula_7 ،جایی که formula_8 حداکثر میانگین پاداش است، formula_9 ، و formula_10 پاداش در دور "t" است."استراتژی صفر پشیمانی استراتژی" است که میانگین پشیمانی آن در هر راند formula_11 وقتی تعداد دورهای بازی شده به بی نهایت میل می‌کند با احتمال 1 به صفر میل می‌کند. به طور شهودی، استراتژی‌های بدون پشیمانی تضمین می‌شوند که اگر راندهای کافی بازی شوند، به یک استراتژی بهینه (الزاماً منحصربه‌فرد) همگرا می‌شوند.تغییرات.یک فرمول متداول، "راهزن چند دست دودویی یا راهزن" "چند دست برنولی است" که یک جایزه با احتمال formula_12 صادر می‌کند و در غیر این صورت پاداش صفر است.فرمول دیگری از راهزن چند دشت دارای هر اهرم نشان دهنده یک ماشین مارکوف مستقل است. هر بار که دستگاه خاصی بازی می‌شود، وضعیت آن دستگاه به دستگاه جدیدی می‌رود که بر اساس احتمالات تکامل حالت مارکوف انتخاب می‌شود. بسته به وضعیت فعلی دستگاه یک پاداش وجود دارد. در یک تعمیم به نام "مسئله راهزن بی‌قرار"، حالت‌های دستگاه‌های بازی نشده نیز می تواند در طول زمان تکامل یابد. همچنین در مورد سیستم‌هایی که تعداد انتخاب‌ها (در مورد اینکه کدام دستگاه بازی شود) در طول زمان افزایش می‌یابد، بحث شده است.محققان علوم کامپیوتر راهزنان چند دست را تحت بدترین مفروضات (worst-case) مورد مطالعه قرار داده‌اند و الگوریتم‌هایی را برای به حداقل رساندن پشیمانی در زمانی متناهی و نامتناهی برای بازدهی اهرم‌های تصادفی &lt;ref name="doi10.1023/A:1013689704352"&gt;&lt;/ref&gt; و غیر تصادفی به دست آورده‌اند.استراتژی‌های راهزن.یک پیشرفت بزرگ، ایجاد استراتژی‌ها یا سیاست‌های انتخاب بهینه جمعیت (که دارای حداکثر نرخ هم‌گرایی یکنواخت با جمعیت با بالاترین میانگین هستند) در کار شرح داده شده در زیر است.راه حل‌های بهینه.در مقاله "قوانین تخصیص تطبیقی کارآمد مجانبی"، لای و رابینز (به دنبال مقالات رابینز و همکارانش که به رابینز در سال 1952 بازمی‌گردند) سیاست‌های انتخاب جمعیت همگرا را ارائه کردند که سریع‌ترین نرخ همگرایی را (به جمعیت با بالاترین میانگین) برای حالتی که توزیع پاداش جمعیت خانواده نمایی یک پارامتری است، دارد. سپس در کاتهاکیس و رابینز ساده‌سازی خط‌مشی و اثبات اصلی برای مورد جمعیت‌های عادی با واریانس‌های شناخته شده ارائه شد. پیشرفت قابل توجه بعدی توسط Burnetas و Katehakis در مقاله "سیاست‌های تطبیقی بهینه برای مسائل تخصیص متوالی"، به دست آمد، جایی که سیاست‌های مبتنی بر شاخص با حداکثر نرخ همگرایی یکنواخت، تحت شرایط عمومی تر که شامل مواردی است که در آن توزیع‌ها وجود دارد، ساخته شد. نتایج هر جمعیت به بردار پارامترهای ناشناخته بستگی دارد. Burnetas و Katehakis همچنین یک راه حل صریح برای مورد مهمی ارائه کردند که در آن توزیع نتایج از توزیع‌های گسسته و تک‌متغیره دلخواه (یعنی ناپارامتریک) پیروی می‌کند.بعداً در «سیاست‌های تطبیقی بهینه برای فرآیندهای تصمیم مارکوف» بورنتاس و کاتهاکیس مدل بسیار بزرگ‌تری از فرآیندهای تصمیم‌گیری مارکوف را تحت اطلاعات محدود مطالعه کردند، جایی که قانون گذار و/یا پاداش‌ یک دوره ممکن است به پارامترهای ناشناخته بستگی داشته باشد. در این کار، نویسندگان یک فرم صریح برای یک کلاس از سیاست‌های تطبیقی با ویژگی‌های نرخ همگرایی حداکثری یکنواخت برای کل پاداش افق محدود مورد انتظار تحت مفروضات کافی فضاهای کنش حالت محدود و کاهش‌ناپذیری قانون گذار ارائه کردند. یکی از ویژگی‌های اصلی این سیاست‌ها این است که انتخاب اقدامات، در هر حالت و دوره زمانی، بر اساس شاخص‌هایی است که تورم‌های سمت راست معادلات میانگین تخمینی بهینه پاداش هستند. این تورم‌ها اخیراً در کار تواری و بارتلت، اورتنر فیلیپی، کاپی، و گاریویه و هوندا و تاکمورا، رویکرد خوش‌بینانه نامیده می‌شوند.برای راهزنان چند دست برنولی، پیلارسکی و همکاران روش‌های محاسباتی استخراج راه‌حل‌های کاملاً بهینه (نه فقط مجانبی) را با استفاده از برنامه‌نویسی پویا در مقاله "سیاست بهینه برای راهزنان برنولی: محاسبات و الگوریتم" مطالعه کردند. این کار از طریق طرح‌های نمایه‌سازی، جداول جستجو و سایر تکنیک‌ها، راه‌حل‌های بهینه عملاً قابل اجرا را برای راهزنان برنولی ارائه کرد، مشروط بر اینکه افق‌های زمانی و تعداد اهرم‌ها بیش از حد بزرگ نشوند. پیلارسکی و همکاران بعداً این کار را در "پاداش تاخیری راهزنان برنولی: سیاست بهینه و متاالگوریتم پیش بینی کننده PARDI" گسترش داد تا روشی برای تعیین خط مشی بهینه راهزنان برنولی ایجاد کند، زمانی که پاداش ممکن است بلافاصله پس از یک تصمیم آشکار نشود و ممکن است به تاخیر بیفتد. این روش بر محاسبه مقادیر مورد انتظار نتایج پاداش که هنوز آشکار نشده اند و به‌روزرسانی توزیع احتمالات پسین هنگام آشکار شدن پاداش‌ها متکی است.می‌توان راه حل‌های بهینه برای راهزن چند دست برای استخراج ارزش انتخاب‌های حیوانات استفاده کرد. فعالیت نورون‌ها در آمیگدال و جسم مخطط شکمی مقادیر به دست آمده از این سیاست‌ها را رمزگذاری می‌کند و می‌تواند برای رمزگشایی زمانی که حیوانات انتخاب‌های اکتشافی در مقابل استثماری انجام دهند استفاده شود. علاوه بر این، سیاست‌های بهینه رفتار انتخاب حیوانات را بهتر از استراتژی‌های جایگزین پیش‌بینی می‌کنند (که در زیر توضیح داده شده است). این نشان می‌دهد که راه‌حل‌های بهینه برای مسئله راهزن چند دست از نظر بیولوژیکی قابل قبول هستند.راه حل‌های تقریبی.راهبردهای زیادی وجود دارند که راه حل تقریبی برای مسئله راهزن ارائه می‌دهند و می‌توان آنها را در چهار گروه کلی که در زیر شرح داده شده است قرار داد:استراتژی‌های نیمه یکنواخت.استراتژی‌های نیمه یکنواخت اولین (و ساده‌ترین) استراتژی‌هایی بودند که برای حل تقریبی مسئله راهزن کشف شدند. همه آن استراتژی‌ها رفتار حریصانه‌ای دارند که در آن "بهترین" اهرم (بر اساس مشاهدات قبلی) همیشه کشیده می‌شود، مگر زمانی که یک اقدام تصادفی (یکنواخت) انجام شود.استراتژی‌های تطبیق احتمال.استراتژی‌های تطبیق احتمال این ایده را منعکس می‌کند که تعداد کشیدن‌ها برای یک اهرم معین باید "با" احتمال واقعی آن برای بهینه بودن اهرم مطابقت داشته باشد. استراتژی‌های تطبیق احتمال نیز به‌عنوان نمونه‌گیری تامپسون یا راهزنان بیزی شناخته می‌شوند، و اگر بتوانید از توزیع پسین برای مقدار میانگین هر جایگزین نمونه برداری کنید، به‌طور شگفت‌آوری آسان می‌شوند.استراتژی‌های قیمت گذاری.استراتژی‌های قیمت گذاری "قیمتی" را برای هر اهرم تعیین می‌کنند. به عنوان مثال، همانطور که با الگوریتم POKER نشان داده شده است، قیمت می‌تواند مجموع پاداش مورد انتظار به اضافه تخمینی از پاداش‌های اضافی آینده باشد که از طریق دانش اضافی به دست می‌آید. اهرم بالاترین قیمت همیشه کشیده می‌شود.راهزن زمینه‌ای.یک تعمیم مفید از راهزن چند دست، راهزن چند دست زمینه‌ای است. در هر تکرار، یک عامل هنوز باید بین اهرم‌ها انتخاب کند، اما همچنین یک بردار ویژگی d بعدی را می‌بیند، بردار زمینه ای که می‌تواند همراه با پاداش اهرم‌های بازی شده در گذشته برای انتخاب اهرم بازی استفاده کند. با گذشت زمان، هدف یادگیرنده جمع‌آوری اطلاعات کافی در مورد چگونگی ارتباط بردارهای زمینه و پاداش‌ها با یکدیگر است، به طوری که بتواند بهترین اهرم بعدی را با نگاه کردن به بردارهای ویژگی پیش‌بینی کند.راه حل‌های تقریبی برای راهزن زمینه‌ای.استراتژی‌های زیادی وجود دارند که راه‌حلی تقریبی برای مسئله راهزن زمینه‌ای ارائه می‌دهند و می‌توان آن‌ها را در دو دسته کلی به تفصیل در زیر قرار داد.راهزن زمینه‌ای محدود.در عمل، معمولاً هزینه ای مرتبط با منابع مصرف شده توسط هر اقدام وجود دارد و هزینه کل توسط بودجه در بسیاری از کاربردها مانند جمع سپاری و آزمایش‌های بالینی محدود می‌شود. راهزن زمینه‌ای محدود (CCB) چنین مدلی است که هم محدودیت‌های زمانی و هم بودجه را در یک محیط راهزن چند دست در نظر می‌گیرد. A. Badanidiyuru و همکاران. ابتدا راهزن‌های زمینه‌ای را با محدودیت‌های بودجه مورد مطالعه قرار داد، که به آنها راهزن‌های زمینه‌ای منبع نیز می‌گویند و نشان داد که formula_21 پشیمانی دست یافتنی است با این حال، کار آنها بر روی مجموعه محدودی از سیاست‌ها متمرکز است و الگوریتم از نظر محاسباتی ناکارآمد است.یک الگوریتم ساده با پشیمانی لگاریتمی در موارد زیر پیشنهاد شده است: