راهزن چند دست: تفاوت میان نسخهها
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۱: | خط ۱: | ||
[[File:Las Vegas slot machines.jpg|thumb|right|ردیفی از ماشین های بازی در لاس وگاس]] |
|||
در [[نظریه احتمالات]] و [[یادگیری ماشین]]، مسئله راهزن چند دست مسئلهای است که در آن یک مجموعه محدود ثابت از منابع باید بین گزینه های رقابتی تخصیص داده شود به طوری که سود مورد انتظار آنها را به حداکثر رساند، زمانی که ویژگیهای هر انتخاب در زمان تخصیص فقط تا حدی شناخته شده است و ممکن است با گذشت زمان یا با تخصیص منابع به گزینه بهتر درک شود<ref name="Gittins89"> |
|||
{{citation |
|||
| last = Gittins |
|||
| first = J. C. |
|||
| author-link = John C. Gittins |
|||
| isbn = 978-0-471-92059-5 |
|||
| location = Chichester |
|||
| publisher = John Wiley & Sons, Ltd. |
|||
| series = Wiley-Interscience Series in Systems and Optimization. |
|||
| title = Multi-armed bandit allocation indices |
|||
| year = 1989 |
|||
}} |
|||
</ref><ref name="BF"> |
|||
{{citation |
|||
| last1 = Berry |
|||
| first1 = Donald A. |
|||
| author1-link = Don Berry (statistician) |
|||
| last2 = Fristedt |
|||
| first2 = Bert |
|||
| isbn = 978-0-412-24810-8 |
|||
| location = London |
|||
| publisher = Chapman & Hall |
|||
| series = Monographs on Statistics and Applied Probability |
|||
| title = Bandit problems: Sequential allocation of experiments |
|||
| year = 1985 |
|||
}} |
|||
</ref>. این مشکل کلاسیک [[یادگیری تقویتی]] مسئله معاوضه اکتشاف-بهره برداری را توصیف میکند. این نام از تصور یک قمارباز در ردیف ماشین های بازی (که گاهی اوقات به عنوان "راهزنان یک دست" شناخته می شود) می آید که باید تصمیم بگیرد که با کدام دستگاه ها بازی کند، هر دستگاه را چند بار بازی کند و به چه ترتیبی بازی کند و اینکه آیا بازی با دستگاه فعلی را ادامه دهد یا دستگاه دیگری را امتحان کند.مسئله راهزن چند دست نیز در دسته بندی گسترده [[برنامه ریزی تصادفی]] قرار میگیرد<ref name="weber">{{citation |
|||
| last = Weber | first = Richard |
|||
| issue = 4 |
|||
| journal = [[Annals of Applied Probability]] |
|||
| pages = 1024–1033 |
|||
| title = On the Gittins index for multiarmed bandits |
|||
| volume = 2 |
|||
| year = 1992 |
|||
| jstor=2959678 |
|||
| doi = 10.1214/aoap/1177005588| doi-access = free |
|||
}}</ref>. |
|||
[[پرونده:Las_Vegas_slot_machines.jpg|چپ|بندانگشتی| ردیفی از ماشینهای بازی در لاس وگاس]] |
|||
در این مسئله، هر ماشین یک پاداش تصادفی از یک [[توزیع احتمال]] خاص برای آن ماشین ارائه میکند که از قبل مشخص نیست. هدف قمارباز به حداکثر رساندن مجموع پاداشهای بهدستآمده از طریق دنبالهای از کشیدن اهرم است.معاوضه مهم قمارباز در هر آزمایش بین "بهره برداری" از ماشین با بالاترین بازده مورد انتظار و "اکتشاف" برای به دست آوردن اطلاعات بیشتر در مورد بازده مورد انتظار ماشین های دیگر است. معاوضه بین اکتشاف و بهره برداری نیز در [[یادگیری ماشینی]] مشاهده میشود. در عمل، راهزنان چند دست برای مدلسازی مشکلاتی مانند مدیریت پروژههای تحقیقاتی در یک سازمان بزرگ، مانند یک بنیاد علمی یا [[صنایع داروسازی]]، استفاده میشوند.در نسخه های اولیه مشکل، قمارباز بدون هیچ دانش اولیه در مورد ماشین ها شروع میکند. |
|||
در [[نظریه احتمالات|تئوری احتمالات]] و [[یادگیری ماشینی|یادگیری ماشین]] ، '''مسئله راهزن چند دست''' مسئلهای است که در آن مجموعه محدود ثابتی از منابع باید بین گزینههای رقیب تخصیص داده شود. انتخابها به گونهای که سود مورد انتظار آنها را به حداکثر برساند، زمانی که ویژگیهای هر انتخاب در زمان تخصیص فقط تا حدی شناخته شده است و ممکن است با گذشت زمان یا با تخصیص منابع به آن انتخاب، بهتر شناخته شود. |
|||
</ref> این یک مسئله کلاسیک [[یادگیری تقویتی]] است که مسئله معاوضه اکتشاف – بهره برداری را توصیف میزند. این نام از تصور یک [[قمار|قمارباز]] در ردیف دستگاههای بازی گرفته شده است، که باید تصمیم بگیرد که با کدام دستگاهها بازی کند، هر دستگاه را چند مرتبه بازی کند و به چه ترتیبی بازی کند، و آیا با دستگاه فعلی ادامه دهد یا دستگاه دیگری را امتحان کند. <ref name="weber">{{Citation|last=Weber|first=Richard|number=4|journal=[[Annals of Applied Probability]]|pages=1024–1033|title=On the Gittins index for multiarmed bandits|volume=2|year=1992|jstor=2959678|doi=10.1214/aoap/1177005588}}</ref> مسئله راهزن چند دست در دستهبندی برنامه ریزی تصادفی قرار میگیرد. |
|||
در این مسئله، هر دستگاه یک پاداش تصادفی را از یک [[توزیع احتمال]] خاص برای آن دستگاه ارائه میکند، که این توزیع از قبل مشخص نیست. هدف قمارباز به حداکثر رساندن مجموع پاداشهای به دست آمده از طریق دنبالهای از کشیدن اهرمها است. <ref name="Gittins89" /> <ref name="BF" /> معاوضه اساسیای که قمارباز در هر آزمایشی با آن روبرو میشود، بین «استثمار» از دستگاهی است که بالاترین بازدهی مورد انتظار را دارد و «اکتشاف» برای به دست آوردن [[قضیه بیز|اطلاعات]] بیشتر در مورد بازدهی مورد انتظار دستگاههای دیگر است. مبادله بین اکتشاف و بهرهبرداری در [[یادگیری ماشینی|یادگیری ماشین]] بررسی شده است. در عمل، راهزن چند دست برای مدلسازی مسائلی مانند مدیریت پروژههای تحقیقاتی در یک سازمان بزرگ، مانند یک بنیاد علمی یا یک [[صنایع داروسازی|شرکت داروسازی،]] استفاده شده است. <ref name="Gittins89" /> <ref name="BF" /> در نسخههای اولیه مسئله، قمارباز بدون هیچ دانش اولیه در مورد دستگاهها شروع میکند. |
|||
[[هربرت رابینز]]، در سال 1952، با درک اهمیت مسئله، استراتژیهای انتخاب جمعیت همگرا را در "برخی از جنبههای طراحی متوالی آزمایشها" ارائه کرد.این قضیه، [[شاخص گیتینز]]، که برای اولین بار توسط [[جان سی گیتینز]] منتشر شد، یک سیاست بهینه برای به حداکثر رساندن پاداش تخفیف مورد انتظار ارائه میدهد. |
|||
هربرت رابینز در سال 1952، با درک اهمیت مسئله، استراتژیهای انتخاب جمعیت همگرا را در "برخی از جنبههای طراحی متوالی آزمایشها" ساخت. <ref>{{Cite journal|last=Robbins|first=H.|year=1952|title=Some aspects of the sequential design of experiments|journal=Bulletin of the American Mathematical Society|volume=58|issue=5|pages=527–535|doi=10.1090/S0002-9904-1952-09620-8|doi-access=free}}</ref> یک قضیه، شاخص گیتینز ، که برای اولین بار توسط جان سی منتشر شد، یک سیاست بهینه برای به حداکثر رساندن پاداش مورد انتظار ارائه میدهد. <ref>{{Cite journal|last=J. C. Gittins|author-link=John C. Gittins|year=1979|title=Bandit Processes and Dynamic Allocation Indices|journal=Journal of the Royal Statistical Society. Series B (Methodological)|volume=41|issue=2|pages=148–177|doi=10.1111/j.2517-6161.1979.tb01068.x|jstor=2985029}}</ref> |
|||
==انگیزه تجربی== |
|||
== انگیزه تجربی == |
|||
مسئله راهزن چند دست، عاملی را مدل میکند که به طور همزمان تلاش میکند دانش جدیدی (به نام «اکتشاف») به دست آورد و تصمیمات خود را بر اساس دانش موجود (به نام «استثمار») بهینه کند. عامل تلاش می کند این وظایف رقیب را متعادل کند تا ارزش کل آنها را در بازه زمانی در نظر گرفته به حداکثر برساند. کاربردهای عملی زیادی از مدل راهزن وجود دارد، به عنوان مثال: |
|||
[[پرونده:The_Jet_Propulsion_Laboratory_(9416811752).jpg|بندانگشتی| چگونه باید بودجه معینی بین این بخشهای تحقیقاتی توزیع شود تا نتایج به حداکثر برسد؟]] |
|||
*[[کارآزمایی بالینی]] که اثرات درمانهای تجربی مختلف را بررسی میکنند و در عین حال تلفات بیمار را به حداقل میرسانند، |
|||
مسئله راهزن چند دست، عاملی را مدل میکند که به طور همزمان تلاش میکند دانش جدیدی («اکتشاف») به دست آورد و تصمیمات خود را بر اساس دانش موجود («استثمار») بهینه کند. عامل تلاش میکند تا این دو وظیفه رقابتی را متعادل کند تا ارزش کلی آنها را در بازه زمانی در نظر گرفته شده به حداکثر برساند. کاربردهای عملی زیادی از مسئله راهزن وجود دارد، به عنوان نمونه: |
|||
*تلاش های [[مسیریابی تطبیقی]] برای به حداقل رساندن تاخیر در یک شبکه، |
|||
*طراحی سبد مالی |
|||
* [[کارآزمایی بالینی|کارآزماییهای بالینی]] که اثرات درمانهای تجربی مختلف را در عین به حداقل رساندن تلفات بیمار بررسی میکنند، <ref name="Gittins89"> |
|||
در این مثالهای عملی، مسئله مستلزم تعادل حداکثری پاداش بر اساس دانشی است که قبلاً به دست آمده و تلاش برای اقدامات جدید برای افزایش بیشتر دانش است. این به عنوان معاوضه بهره برداری در مقابل اکتشاف در [[یادگیری ماشین]] شناخته می شود. |
|||
{{Citation|last=Gittins|first=J. C.|author-link=John C. Gittins|isbn=978-0-471-92059-5|place=Chichester|publisher=John Wiley & Sons, Ltd.|series=Wiley-Interscience Series in Systems and Optimization.|title=Multi-armed bandit allocation indices|year=1989}}<cite class="citation cs2" data-ve-ignore="true" id="CITEREFGittins1989">[[جان سی گیتینز|Gittins, J. C.]] (1989), ''Multi-armed bandit allocation indices'', Wiley-Interscience Series in Systems and Optimization., Chichester: John Wiley & Sons, Ltd., [[شماره استاندارد بینالمللی کتاب|ISBN]] [[ویژه: منابع کتاب/978-0-471-92059-5|<bdi>978-0-471-92059-5</bdi>]]</cite> |
|||
</ref> <ref name="BF"> |
|||
{{Citation|last=Berry|first=Donald A.|author1-link=Don Berry (statistician)|last2=Fristedt|first2=Bert|isbn=978-0-412-24810-8|place=London|publisher=Chapman & Hall|series=Monographs on Statistics and Applied Probability|title=Bandit problems: Sequential allocation of experiments|year=1985}}<cite class="citation cs2" data-ve-ignore="true" id="CITEREFBerryFristedt1985">[[دان بری|Berry, Donald A.]]; Fristedt, Bert (1985), ''Bandit problems: Sequential allocation of experiments'', Monographs on Statistics and Applied Probability, London: Chapman & Hall, [[شماره استاندارد بینالمللی کتاب|ISBN]] [[ویژه: منابع کتاب/978-0-412-24810-8|<bdi>978-0-412-24810-8</bdi>]]</cite> |
|||
</ref> <ref name="WHP"> |
|||
{{Citation|first=William H.|last=Press|year=2009|title=Bandit solutions provide unified ethical models for randomized clinical trials and comparative effectiveness research|journal=Proceedings of the National Academy of Sciences|volume=106|pages=22387–22392|pmid=20018711|doi=10.1073/pnas.0912378106|number=52|pmc=2793317|postscript=.|bibcode=2009PNAS..10622387P}} |
|||
</ref> <ref name="KD">Press (1986)</ref> |
|||
* تلاشهای مسیریابی تطبیقی برای به حداقل رساندن تاخیر در شبکه، |
|||
* [[سبد سهام|طراحی سبد مالی]] <ref name="BrochuHoffmandeFreitas"> |
|||
{{Citation|last=Brochu|first=Eric|last2=Hoffman|first2=Matthew W.|last3=de Freitas|first3=Nando|arxiv=1009.5419|date=September 2010|title=Portfolio Allocation for Bayesian Optimization|bibcode=2010arXiv1009.5419B}} |
|||
</ref> <ref name="ShenWangJiangZha"> |
|||
{{Citation|last=Shen|first=Weiwei|last2=Wang|first2=Jun|last3=Jiang|first3=Yu-Gang|last4=Zha|first4=Hongyuan|journal=Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI2015)|url=http://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/viewPDFInterstitial/10972/10798|date=2015|title=Portfolio Choices with Orthogonal Bandit Learning}} |
|||
</ref> |
|||
در این مثالهای عملی، مسئله مستلزم رسیدن به حداکثر پاداش بر اساس دانشی است که قبلاً به دست آوردهایم و تلاش برای اقدامات جدید برای افزایش بیشتر دانش است. این به عنوان ''معاوضه بهره برداری در مقابل اکتشاف'' در [[یادگیری ماشینی]] شناخته میشود. |
|||
این مدل همچنین برای کنترل تخصیص پویا منابع به پروژههای مختلف استفاده شده است و به این سؤال پاسخ میدهد که با توجه به عدم اطمینان در مورد دشواری و بازده هر امکان، روی کدام پروژه کار کنیم. |
|||
این مدل برای کنترل تخصیص پویای منابع به پروژههای مختلف استفاده شده است و به این سؤال پاسخ میدهد که با توجه به عدم اطمینان در مورد دشواری و بازدهی هر گزینه، روی کدام پروژه کار شود. <ref name="farias2011irrevocable"> |
|||
{{Citation|title=The irrevocable multiarmed bandit problem|last=Farias|first=Vivek F|first2=Madan|last2=Ritesh|journal=[[Operations Research (journal)|Operations Research]]|volume=59|number=2|pages=383–399|year=2011|doi=10.1287/opre.1100.0891}} |
|||
</ref> |
|||
در ابتدا توسط دانشمندان متفقین در [[جنگ جهانی دوم]] مورد توجه قرار گرفت، اما به قدری غیرقابل حل |
این مسئله در ابتدا توسط دانشمندان متفقین در [[جنگ جهانی دوم]] مورد توجه قرار گرفت، اما به قدری غیرقابل حل بود که به گفته پیتر ویتل ، پیشنهاد شد که این مسئله در بین [[آلمان|آلمانیها]] رها شود تا دانشمندان آلمانی نیز بتوانند وقت خود را برای آن تلف کنند. <ref name="Whittle79"> |
||
{{Citation|last=Whittle|first=Peter|author-link=Peter Whittle (mathematician)|journal=[[Journal of the Royal Statistical Society]]|series=Series B|title=Discussion of Dr Gittins' paper|volume=41|number=2|pages=148–177|year=1979|doi=10.1111/j.2517-6161.1979.tb01069.x}} |
|||
</ref> |
|||
نسخهای از مسئله که اکنون معمولاً مورد بررسی قرار میگیرد توسط هربرت رابینز در سال 1952 فرموله شده است. |
|||
== مدل راهزن چند دستی == |
|||
راهزن چند دستی (کوتاه: MAB) را میتوان به عنوان مجموعه ای از [[توزیع احتمال|توزیع]]<nowiki/>های واقعی دید. <math>B = \{R_1, \dots ,R_K\}</math> ، هر توزیع با پاداشهای ارائه شده توسط یکی از <math>K \in \mathbb{N}^+</math> اهرم مرتبط است. اگر <math>\mu_1, \dots, \mu_K</math> مقادیر میانگین مرتبط با این توزیعهای پاداش باشد، قمارباز به طور مکرر در هر دور یک اهرم بازی میکند و پاداش مربوطه را مشاهده میکند. هدف این است که مجموع پاداشهای جمع آوری شده را به حداکثر برساند. افق <math>H</math> تعداد دورهایی است که باید انجام شود. مسئله راهزن به طور رسمی معادل [[فرایندهای تصمیمگیری مارکوف|فرآیند تصمیم گیری مارکوف]] یک حالته است. پشیمانی <math>\rho</math> بعد از <math>T</math> دور به عنوان تفاوت مورد انتظار بین مجموع پاداش مرتبط با یک استراتژی بهینه و مجموع پاداشهای جمع آوری شده تعریف میشود: |
|||
<math>\rho = T \mu^* - \sum_{t=1}^T \widehat{r}_t</math> ، |
|||
==مدل راهزن چند دست== |
|||
راهزن چند دست را میتوان مجموعه ای از توزیع های واقعی <math>B = \{R_1, \dots ,R_K\}</math> دانست که هر توزیع با پاداش های ارائه شده توسط یکی از <math>K \in \mathbb{N}^+</math> اهرم مرتبط است. اگر <math>\mu_1, \dots , \mu_K</math> مقادیر میانگین مرتبط با این توزیعهای پاداش باشند. قمارباز به طور مکرر در هر دور یک اهرم بازی می کند و پاداش مربوطه را مشاهده می کند. هدف به حداکثر رساندن مجموع پاداش های جمع آوری شده است. مسئله راهزن به طور رسمی معادل فرآیند [[تصمیم گیری مارکوف]] تک راسی است. پشیمانی <math>\rho</math> بعد از دورهای <math>T</math> به عنوان تفاوت مورد انتظار بین مجموع پاداش مرتبط با یک استراتژی بهینه و مجموع پاداشهای جمعآوریشده به شکل زیر تعریف میشود: |
|||
<math>\ |
جایی که <math>\mu^*</math> حداکثر میانگین پاداش است، <math>\mu^* = \max_k \{ \mu_k \}</math> ، و <math>\widehat{r}_t</math> پاداش در دور ''t'' است. |
||
''استراتژی صفر پشیمانی استراتژی'' است که میانگین پشیمانی آن در هر راند <math>\rho / T</math> وقتی تعداد دورهای بازی شده به بی نهایت میل میکند با احتمال 1 به صفر میل میکند. به طور شهودی، استراتژیهای بدون پشیمانی تضمین میشوند که اگر راندهای کافی بازی شوند، به یک استراتژی بهینه (الزاماً منحصربهفرد) همگرا میشوند. |
|||
که در آن <math>\mu^*</math> حداکثر میانگین پاداش است، <math>\mu^* = \max_k \{ \mu_k \}</math> و <math>\widehat{r}_t</math> پاداش در دور t است. |
|||
== تغییرات == |
|||
استراتژی صفر پشیمانی استراتژی است که میانگین پشیمانی آن در هر دور <math>\rho / T</math> با احتمال 1، زمانی که تعداد راندهای بازی شده به بی نهایت میل می کند، به صفر می رسد.به طور شهودی، استراتژیهای بدون پشیمانی تضمین میشوند که اگر راندهای کافی بازی شود، به یک استراتژی بهینه (نه لزوما منحصر به فرد) همگرا میشوند. |
|||
یک فرمول متداول، ''راهزن چند دست دودویی یا راهزن'' ''چند دست برنولی است'' که یک جایزه با احتمال <math>p</math> صادر میکند و در غیر این صورت پاداش صفر است. |
|||
فرمول دیگری از راهزن چند دشت دارای هر اهرم نشان دهنده یک ماشین مارکوف مستقل است. هر بار که دستگاه خاصی بازی میشود، وضعیت آن دستگاه به دستگاه جدیدی میرود که بر اساس احتمالات تکامل حالت مارکوف انتخاب میشود. بسته به وضعیت فعلی دستگاه یک پاداش وجود دارد. در یک تعمیم به نام "مسئله راهزن بیقرار"، حالتهای دستگاههای بازی نشده نیز می تواند در طول زمان تکامل یابد. <ref name="Whittle88"> |
|||
{{Citation|last=Whittle|first=Peter|author-link=Peter Whittle (mathematician)|mr=974588|journal=Journal of Applied Probability|pages=287–298|title=Restless bandits: Activity allocation in a changing world|volume=25A|year=1988|doi=10.2307/3214163|jstor=3214163}} |
|||
</ref> همچنین در مورد سیستمهایی که تعداد انتخابها (در مورد اینکه کدام دستگاه بازی شود) در طول زمان افزایش مییابد، بحث شده است. <ref name="Whittle81"> |
|||
{{Citation|last=Whittle|first=Peter|author-link=Peter Whittle (mathematician)|doi=10.1214/aop/1176994469|journal=Annals of Probability|pages=284–292|title=Arm-acquiring bandits|volume=9|year=1981|number=2}} |
|||
</ref> |
|||
محققان علوم کامپیوتر راهزنان چند دست را تحت بدترین مفروضات (worst-case) مورد مطالعه قرار دادهاند و الگوریتمهایی را برای به حداقل رساندن پشیمانی در زمانی متناهی و نامتناهی برای بازدهی اهرمهای تصادفی <ref name="doi10.1023/A:1013689704352">{{Cite journal|last=Auer|first=P.|last2=Cesa-Bianchi|first2=N.|last3=Fischer|first3=P.|year=2002|title=Finite-time Analysis of the Multiarmed Bandit Problem|journal=Machine Learning|volume=47|issue=2/3|pages=235–256|doi=10.1023/A:1013689704352|doi-access=free}}</ref> و غیر تصادفی <ref>{{Cite journal|last=Auer|first=P.|last2=Cesa-Bianchi|first2=N.|last3=Freund|first3=Y.|last4=Schapire|first4=R. E.|year=2002|title=The Nonstochastic Multiarmed Bandit Problem|journal=[[SIAM Journal on Computing|SIAM J. Comput.]]|volume=32|issue=1|pages=48–77|citeseerx=10.1.1.130.158|doi=10.1137/S0097539701398375}}</ref> به دست آوردهاند. |
|||
==استراتژیها== |
|||
یک پیشرفت قابل توجه ساخت استراتژی ها یا سیاست های انتخاب جمعیت بهینه (که دارای حداکثر نرخ همگرایی یکنواخت با جمعیت با بالاترین میانگین هستند) بود. |
|||
== استراتژیهای راهزن == |
|||
===راه حلهای بهینه=== |
|||
یک پیشرفت بزرگ، ایجاد استراتژیها یا سیاستهای انتخاب بهینه جمعیت (که دارای حداکثر نرخ همگرایی یکنواخت با جمعیت با بالاترین میانگین هستند) در کار شرح داده شده در زیر است. |
|||
در مقاله "قوانین تخصیص تطبیقی کارآمد مجانبی"، لای و رابینز <ref>{{cite journal | last1 = Lai | first1 = T.L. | last2 = Robbins | first2 = H. | year = 1985 | title = Asymptotically efficient adaptive allocation rules | journal = Advances in Applied Mathematics | volume = 6 | issue = 1| pages =4–22 | doi = 10.1016/0196-8858(85)90002-8 | doi-access = free }}</ref> (به دنبال مقالات رابینز و همکارانش که به رابینز در سال 1952 بازمیگردند) سیاستهای انتخاب جمعیت همگرا را ایجاد کردند که دارای سریعترین نرخ همگرایی (به جمعیت با بالاترین میانگین) برای حالتی که توزیع پاداش جمعیت به صورت نمایی یک پارامتری است. سپس در کاتهاکیس و رابینز <ref>{{cite journal | last1 = Katehakis | first1 = M.N. | last2 = Robbins | first2 = H. | year = 1995 | title = Sequential choice from several populations | journal = Proceedings of the National Academy of Sciences of the United States of America | volume = 92 | issue = 19| pages =8584–5 | doi = 10.1073/pnas.92.19.8584 | pmid = 11607577 | pmc = 41010 | bibcode = 1995PNAS...92.8584K| doi-access = free }}</ref> سادهسازی خطمشی و اثبات اصلی برای مورد جمعیتهای عادی با واریانسهای شناخته شده ارائه شد. پیشرفت قابل توجه بعدی توسط Burnetas و Katehakis در مقاله "سیاست های تطبیقی بهینه برای مشکلات تخصیص متوالی" به دست آمد، <ref>{{cite journal | last1 = Burnetas | first1 = A.N. | last2 = Katehakis | first2 = M.N. | year = 1996 | title = Optimal adaptive policies for sequential allocation problems | journal = Advances in Applied Mathematics | volume = 17 | issue = 2| pages =122–142 | doi = 10.1006/aama.1996.0007 | doi-access = free }}</ref> که در آن خط مشی های مبتنی بر شاخص با حداکثر نرخ همگرایی یکنواخت ساخته شدند، تحت شرایط عمومی تر که شامل موردی می شود که در آن توزیع نتایج از هر جمعیت به بردار پارامترهای ناشناخته بستگی دارد. بورنتاس و کاتهاکیس (1996) همچنین راه حلی صریح برای مورد مهمی ارائه کردند که در آن توزیع نتایج از توزیع های گسسته و تک متغیره دلخواه (به عنوان مثال، غیرپارامتری) پیروی میکند. |
|||
=== راه حلهای بهینه === |
|||
در مقاله "قوانین تخصیص تطبیقی کارآمد مجانبی"، لای و رابینز <ref>{{Cite journal|last=Lai|first=T.L.|last2=Robbins|first2=H.|year=1985|title=Asymptotically efficient adaptive allocation rules|journal=Advances in Applied Mathematics|volume=6|issue=1|pages=4–22|doi=10.1016/0196-8858(85)90002-8|doi-access=free}}</ref> (به دنبال مقالات رابینز و همکارانش که به رابینز در سال 1952 بازمیگردند) سیاستهای انتخاب جمعیت همگرا را ارائه کردند که سریعترین نرخ همگرایی را (به جمعیت با بالاترین میانگین) برای حالتی که توزیع پاداش جمعیت خانواده نمایی یک پارامتری است، دارد. سپس در کاتهاکیس و رابینز <ref>{{Cite journal|last=Katehakis|first=M.N.|last2=Robbins|first2=H.|year=1995|title=Sequential choice from several populations|journal=Proceedings of the National Academy of Sciences of the United States of America|volume=92|issue=19|pages=8584–5|bibcode=1995PNAS...92.8584K|doi=10.1073/pnas.92.19.8584|pmc=41010|pmid=11607577|doi-access=free}}</ref> سادهسازی خطمشی و اثبات اصلی برای مورد جمعیتهای عادی با واریانسهای شناخته شده ارائه شد. پیشرفت قابل توجه بعدی توسط Burnetas و Katehakis در مقاله "سیاستهای تطبیقی بهینه برای مسائل تخصیص متوالی"، <ref>{{Cite journal|last=Burnetas|first=A.N.|last2=Katehakis|first2=M.N.|year=1996|title=Optimal adaptive policies for sequential allocation problems|journal=Advances in Applied Mathematics|volume=17|issue=2|pages=122–142|doi=10.1006/aama.1996.0007|doi-access=free}}</ref> به دست آمد، جایی که سیاستهای مبتنی بر شاخص با حداکثر نرخ همگرایی یکنواخت، تحت شرایط عمومی تر که شامل مواردی است که در آن توزیعها وجود دارد، ساخته شد. نتایج هر جمعیت به بردار پارامترهای ناشناخته بستگی دارد. Burnetas و Katehakis همچنین یک راه حل صریح برای مورد مهمی ارائه کردند که در آن توزیع نتایج از توزیعهای گسسته و تکمتغیره دلخواه (یعنی ناپارامتریک) پیروی میکند. |
|||
بعداً در «سیاستهای تطبیقی |
بعداً در «سیاستهای تطبیقی بهینه برای فرآیندهای تصمیم مارکوف» <ref>{{Cite journal|last=Burnetas|first=A.N.|last2=Katehakis|first2=M.N.|year=1997|title=Optimal adaptive policies for Markov decision processes|journal=Math. Oper. Res.|volume=22|issue=1|pages=222–255|doi=10.1287/moor.22.1.222}}</ref> بورنتاس و کاتهاکیس مدل بسیار بزرگتری از فرآیندهای تصمیمگیری مارکوف را تحت اطلاعات محدود مطالعه کردند، جایی که قانون گذار و/یا پاداش یک دوره ممکن است به پارامترهای ناشناخته بستگی داشته باشد. در این کار، نویسندگان یک فرم صریح برای یک کلاس از سیاستهای تطبیقی با ویژگیهای نرخ همگرایی حداکثری یکنواخت برای کل پاداش افق محدود مورد انتظار تحت مفروضات کافی فضاهای کنش حالت محدود و کاهشناپذیری قانون گذار ارائه کردند. یکی از ویژگیهای اصلی این سیاستها این است که انتخاب اقدامات، در هر حالت و دوره زمانی، بر اساس شاخصهایی است که تورمهای سمت راست معادلات میانگین تخمینی بهینه پاداش هستند. این تورمها اخیراً در کار تواری و بارتلت، <ref>{{Cite journal|last=Tewari|first=A.|last2=Bartlett|first2=P.L.|year=2008|title=Optimistic linear programming gives logarithmic regret for irreducible MDPs|url=http://books.nips.cc/papers/files/nips20/NIPS2007_0673.pdf|journal=Advances in Neural Information Processing Systems|volume=20|citeseerx=10.1.1.69.5482}}</ref> اورتنر <ref>{{Cite journal|last=Ortner|first=R.|year=2010|title=Online regret bounds for Markov decision processes with deterministic transitions|journal=Theoretical Computer Science|volume=411|issue=29|pages=2684–2695|doi=10.1016/j.tcs.2010.04.005|doi-access=free}}</ref> فیلیپی، کاپی، و گاریویه <ref>Filippi, S. and Cappé, O. and Garivier, A. (2010). "Online regret bounds for Markov decision processes with deterministic transitions", ''Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on'', pp. 115–122</ref> و هوندا و تاکمورا، رویکرد خوشبینانه نامیده میشوند. <ref>{{Cite journal|last=Honda|first=J.|last2=Takemura|first2=A.|year=2011|title=An asymptotically optimal policy for finite support models in the multi-armed bandit problem|journal=Machine Learning|volume=85|issue=3|pages=361–391|arxiv=0905.2776|doi=10.1007/s10994-011-5257-4}}</ref> |
||
برای راهزنان چند دست برنولی، پیلارسکی و همکاران |
برای راهزنان چند دست برنولی، پیلارسکی و همکاران روشهای محاسباتی استخراج راهحلهای کاملاً بهینه (نه فقط مجانبی) را با استفاده از برنامهنویسی پویا در مقاله "سیاست بهینه برای راهزنان برنولی: محاسبات و الگوریتم" مطالعه کردند. <ref>{{Cite journal|last=Pilarski|first=Sebastian|last2=Pilarski|first2=Slawomir|last3=Varró|first3=Dániel|date=February 2021|title=Optimal Policy for Bernoulli Bandits: Computation and Algorithm Gauge|url=https://ieeexplore.ieee.org/document/9408359|journal=IEEE Transactions on Artificial Intelligence|volume=2|issue=1|pages=2–17|doi=10.1109/TAI.2021.3074122|issn=2691-4581|doi-access=free}}</ref> این کار از طریق طرحهای نمایهسازی، جداول جستجو و سایر تکنیکها، راهحلهای بهینه عملاً قابل اجرا را برای راهزنان برنولی ارائه کرد، مشروط بر اینکه افقهای زمانی و تعداد اهرمها بیش از حد بزرگ نشوند. پیلارسکی و همکاران بعداً این کار را در "پاداش تاخیری راهزنان برنولی: سیاست بهینه و متاالگوریتم پیش بینی کننده PARDI" <ref>{{Cite journal|last=Pilarski|first=Sebastian|last2=Pilarski|first2=Slawomir|last3=Varro|first3=Daniel|date=2021|title=Delayed Reward Bernoulli Bandits: Optimal Policy and Predictive Meta-Algorithm PARDI|url=https://ieeexplore.ieee.org/document/9582844|journal=IEEE Transactions on Artificial Intelligence|volume=3|issue=2|pages=152–163|doi=10.1109/TAI.2021.3117743|issn=2691-4581|doi-access=free}}</ref> گسترش داد تا روشی برای تعیین خط مشی بهینه راهزنان برنولی ایجاد کند، زمانی که پاداش ممکن است بلافاصله پس از یک تصمیم آشکار نشود و ممکن است به تاخیر بیفتد. این روش بر محاسبه مقادیر مورد انتظار نتایج پاداش که هنوز آشکار نشده اند و بهروزرسانی توزیع احتمالات پسین هنگام آشکار شدن پاداشها متکی است. |
||
میتوان راه حلهای بهینه برای راهزن چند دست <ref>{{Cite journal|last=Averbeck|first=B.B.|year=2015|title=Theory of choice in bandit, information sampling, and foraging tasks|journal=PLOS Computational Biology|volume=11|issue=3|pages=e1004164|bibcode=2015PLSCB..11E4164A|doi=10.1371/journal.pcbi.1004164|pmc=4376795|pmid=25815510}}</ref> برای استخراج ارزش انتخابهای حیوانات استفاده کرد. فعالیت نورونها در آمیگدال و جسم مخطط شکمی مقادیر به دست آمده از این سیاستها را رمزگذاری میکند و میتواند برای رمزگشایی زمانی که حیوانات انتخابهای اکتشافی در مقابل استثماری انجام دهند استفاده شود. علاوه بر این، سیاستهای بهینه رفتار انتخاب حیوانات را بهتر از استراتژیهای جایگزین پیشبینی میکنند (که در زیر توضیح داده شده است). این نشان میدهد که راهحلهای بهینه برای مسئله راهزن چند دست از نظر بیولوژیکی قابل قبول هستند. <ref>{{Cite journal|last=Costa|first=V.D.|last2=Averbeck|first2=B.B.|year=2019|title=Subcortical Substrates of Explore-Exploit Decisions in Primates|url=|journal=Neuron|volume=103|issue=3|pages=533–535|doi=10.1016/j.neuron.2019.05.017|pmc=6687547|pmid=31196672}}</ref> |
|||
* '''UCBC (محدودههای بالای اطمینان تاریخی با خوشهها):''' الگوریتم UCB را برای یک تنظیم جدید به گونه ای تطبیق میدهد که بتواند هم خوشه بندی و هم اطلاعات تاریخی را در خود جای دهد. این الگوریتم مشاهدات تاریخی را با استفاده از هر دو در محاسبه پاداش میانگین مشاهده شده و عبارت عدم قطعیت ترکیب میکند. این الگوریتم اطلاعات خوشهبندی را با بازی در دو سطح ترکیب میکند: ابتدا انتخاب یک خوشه با استفاده از یک استراتژی شبیه به UCB در هر مرحله زمانی، و متعاقبا انتخاب یک اهرم از درون خوشه، دوباره با استفاده از یک استراتژی مشابه UCB. |
|||
== جستارهای وابسته == |
|||
{{چندستونه|cols=2}} |
|||
* [[شاخص گیتینز]] |
|||
* [[الگوریتم حریصانه]] |
|||
* [[توقف بهینه]] |
|||
* [[برنامهریزی تصادفی]] |
|||
=== راه حلهای تقریبی === |
|||
{{Div col end}} |
|||
راهبردهای زیادی وجود دارند که راه حل تقریبی برای مسئله راهزن ارائه میدهند و میتوان آنها را در چهار گروه کلی که در زیر شرح داده شده است قرار داد: |
|||
==== استراتژیهای نیمه یکنواخت ==== |
|||
== منابع == |
|||
استراتژیهای نیمه یکنواخت اولین (و سادهترین) استراتژیهایی بودند که برای حل تقریبی مسئله راهزن کشف شدند. همه آن استراتژیها رفتار [[الگوریتم حریصانه|حریصانهای]] دارند که در آن ''بهترین'' اهرم (بر اساس مشاهدات قبلی) همیشه کشیده میشود، مگر زمانی که یک اقدام تصادفی (یکنواخت) انجام شود. |
|||
{{پانویس|۲}} |
|||
[[رده:برنامهنویسی پویا]] |
|||
* '''استراتژی اپسیلون حریص''' : <ref>Sutton, R. S. & Barto, A. G. 1998 Reinforcement learning: an introduction. Cambridge, MA: MIT Press.</ref> بهترین اهرم برای نسبت <math>1 - \epsilon</math> از آزمایشها انتخاب میشود، و یک اهرم به طور تصادفی (با احتمال یکنواخت) برای یک نسبت <math>\epsilon</math> انتخاب میشود. یک مقدار پارامتر متداول ممکن است <math>\epsilon = 0.1</math> باشد، اما بسته به شرایط و تمایلات میتواند بسیار متفاوت باشد. |
|||
[[رده:یادگیری تقویتی]] |
|||
* '''استراتژی اپسیلون اول'''{{مدرک|date=March 2015}} : مرحله اکتشاف خالص با مرحله بهره برداری خالص دنبال میشود. برای <math>N</math> آزمایش در مجموع، مرحله اکتشاف <math>\epsilon N</math> آزمایشها را اشغال میکند و مرحله بهره برداری <math>(1 - \epsilon) N</math> آزمایش. در طول مرحله اکتشاف، یک اهرم به طور تصادفی انتخاب میشود (با احتمال یکنواخت). در طول مرحله بهره برداری، بهترین اهرم همیشه انتخاب میشود. |
|||
* '''استراتژی کاهش اپسیلون'''{{مدرک|date=March 2015}} : شبیه به استراتژی epsilon-greedy، با این تفاوت که ارزش <math>\epsilon</math> با پیشرفت آزمایش کاهش مییابد و در نتیجه رفتار بسیار اکتشافی در شروع و رفتار بسیار استثمارگرانه در پایان ایجاد میشود. |
|||
* '''استراتژی تطبیقی حریصانه-اپسیلون بر اساس تفاوتهای ارزشی (VDBE)''' : مشابه استراتژی کاهش اپسیلون است، با این تفاوت که اپسیلون بر اساس پیشرفت یادگیری به جای تنظیم دستی کاهش مییابد (Tokic، 2010). <ref name="Tokic2010"> |
|||
{{Citation|last=Tokic|first=Michel|chapter=Adaptive ε-greedy exploration in reinforcement learning based on value differences|doi=10.1007/978-3-642-16111-7_23|pages=203–210|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|title=KI 2010: Advances in Artificial Intelligence|volume=6359|year=2010|chapter-url=http://www.tokic.com/www/tokicm/publikationen/papers/AdaptiveEpsilonGreedyExploration.pdf|isbn=978-3-642-16110-0}}. |
|||
</ref> نوسانات زیاد در برآورد ارزش، منجر به اپسیلون بالا (اکتشاف زیاد، بهره برداری کم) میشود. نوسانات کم به یک اپسیلون کم (اکتشاف کم، بهره برداری زیاد) منجر میشود. بهبودهای بیشتر را میتوان با انتخاب کنش با وزن نرم افزار در مورد اقدامات اکتشافی به دست آورد ( [[بیشینه هموار|Tokic]] & Palm, 2011). <ref name="TokicPalm2011"> |
|||
{{Citation|last=Tokic|first=Michel|last2=Palm|first2=Günther|chapter=Value-Difference Based Exploration: Adaptive Control Between Epsilon-Greedy and Softmax|pages=335–346|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|title=KI 2011: Advances in Artificial Intelligence|volume=7006|year=2011|chapter-url=http://www.tokic.com/www/tokicm/publikationen/papers/KI2011.pdf|isbn=978-3-642-24455-1}}. |
|||
</ref> |
|||
* '''استراتژی تطبیقی epsilon-greedy مبتنی بر گروههای بیزی (Epsilon-BMC)''' : یک استراتژی انطباق اپسیلون تطبیقی برای یادگیری تقویتی مشابه VBDE، با تضمینهای همگرایی یکنواخت است. در این چارچوب، پارامتر اپسیلون بهعنوان انتظار توزیع پسینی در نظر گرفته میشود که وزن یک عامل حریص (که کاملاً به پاداش آموخته شده اعتماد دارد) و عامل یادگیری یکنواخت (که به پاداش آموخته شده بیاعتماد است) دارد. این توزیع پسین با استفاده از یک توزیع بتا مناسب با فرض نرمال بودن پاداشهای مشاهده شده تقریب زده میشود. به منظور پرداختن به خطر احتمالی کاهش سریع اپسیلون، عدم قطعیت در واریانس پاداش آموخته شده نیز با استفاده از یک مدل گامای نرمال مدلسازی و بهروزرسانی میشود. (گیملفارب و همکاران، 2019). <ref name="Gimelfarb2019"> |
|||
{{Citation|last=Gimelfarb|first=Michel|last2=Sanner|first2=Scott|last3=Lee|first3=Chi-Guhn|chapter=ε-BMC: A Bayesian Ensemble Approach to Epsilon-Greedy Exploration in Model-Free Reinforcement Learning|pages=162|publisher=AUAI Press|title=Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence|year=2019|chapter-url=http://auai.org/uai2019/proceedings/papers/162.pdf}}. |
|||
</ref> |
|||
* '''استراتژی متنی-اپسیلون-حریصانه: مشابه استراتژی''' اپسیلون-حریصانه، با این تفاوت که ارزش <math>\epsilon</math> با توجه به وضعیت در فرآیندهای آزمایشی محاسبه میشود، که به الگوریتم اجازه میدهد Context-Aware باشد. این مبتنی بر اکتشاف/استثمار پویا است و میتواند با تصمیمگیری اینکه کدام موقعیت برای اکتشاف یا بهرهبرداری مناسبتر است، به طور انطباقی بین دو جنبه تعادل برقرار کند، که منجر به رفتار بسیار اکتشافی زمانی که موقعیت بحرانی نیست و رفتار بسیار استثمارگرانه در موقعیت بحرانی میشود. <ref name="Bouneffouf2012"> |
|||
{{Citation|last=Bouneffouf|first=D.|last2=Bouzeghoub|first2=A.|last3=Gançarski|first3=A. L.|doi=10.1007/978-3-642-34487-9_40|chapter=A Contextual-Bandit Algorithm for Mobile Context-Aware Recommender System|title=Neural Information Processing|series=Lecture Notes in Computer Science|volume=7665|pages=324|year=2012|isbn=978-3-642-34486-2}} |
|||
</ref> |
|||
==== استراتژیهای تطبیق احتمال ==== |
|||
استراتژیهای تطبیق احتمال این ایده را منعکس میکند که تعداد کشیدنها برای یک اهرم معین باید ''با'' احتمال واقعی آن برای بهینه بودن اهرم مطابقت داشته باشد. استراتژیهای تطبیق احتمال نیز بهعنوان نمونهگیری تامپسون یا راهزنان بیزی شناخته میشوند، <ref name="Scott2010"> |
|||
{{Citation|last=Scott|first=S.L.|doi=10.1002/asmb.874|journal=Applied Stochastic Models in Business and Industry|pages=639–658|title=A modern Bayesian look at the multi-armed bandit|volume=26|year=2010|number=2}} |
|||
</ref> <ref name="cl11thompson"> |
|||
{{Citation|last=Olivier Chapelle|last2=Lihong Li|title=An empirical evaluation of Thompson sampling|journal=Advances in Neural Information Processing Systems 24 (NIPS)|pages=2249–2257|year=2011|volume=24|publisher=Curran Associates|url=http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling}} |
|||
</ref> و اگر بتوانید از توزیع پسین برای مقدار میانگین هر جایگزین نمونه برداری کنید، بهطور شگفتآوری آسان میشوند. |
|||
==== استراتژیهای قیمت گذاری ==== |
|||
استراتژیهای قیمت گذاری ''قیمتی'' را برای هر اهرم تعیین میکنند. به عنوان مثال، همانطور که با الگوریتم POKER نشان داده شده است، <ref name="Vermorel2005"> |
|||
{{Citation|url=http://bandit.sourceforge.net/Vermorel2005poker.pdf|last=Vermorel|first=Joannes|last2=Mohri|first2=Mehryar|publisher=Springer|series=In European Conference on Machine Learning|pages=437–448|title=Multi-armed bandit algorithms and empirical evaluation|year=2005}}<cite class="citation cs2" data-ve-ignore="true" id="CITEREFVermorelMohri2005">Vermorel, Joannes; Mohri, Mehryar (2005), [http://bandit.sourceforge.net/Vermorel2005poker.pdf ''Multi-armed bandit algorithms and empirical evaluation''] <span class="cs1-format">(PDF)</span>, In European Conference on Machine Learning, Springer, pp. 437–448</cite> |
|||
</ref> قیمت میتواند مجموع پاداش مورد انتظار به اضافه تخمینی از پاداشهای اضافی آینده باشد که از طریق دانش اضافی به دست میآید. اهرم بالاترین قیمت همیشه کشیده میشود. |
|||
== راهزن زمینهای == |
|||
یک تعمیم مفید از راهزن چند دست، راهزن چند دست زمینهای است. در هر تکرار، یک عامل هنوز باید بین اهرمها انتخاب کند، اما همچنین یک بردار ویژگی d بعدی را میبیند، بردار زمینه ای که میتواند همراه با پاداش اهرمهای بازی شده در گذشته برای انتخاب اهرم بازی استفاده کند. با گذشت زمان، هدف یادگیرنده جمعآوری اطلاعات کافی در مورد چگونگی ارتباط بردارهای زمینه و پاداشها با یکدیگر است، به طوری که بتواند بهترین اهرم بعدی را با نگاه کردن به بردارهای ویژگی پیشبینی کند. <ref name="Langford2008"> |
|||
{{Citation|chapter-url=http://papers.nips.cc/paper/3178-the-epoch-greedy-algorithm-for-multi-armed-bandits-with-side-information|last=Langford|first=John|last2=Zhang|first2=Tong|publisher=Curran Associates, Inc.|pages=817–824|title=Advances in Neural Information Processing Systems 20|chapter=The Epoch-Greedy Algorithm for Contextual Multi-armed Bandits|year=2008|volume=20}} |
|||
</ref> |
|||
=== راه حلهای تقریبی برای راهزن زمینهای === |
|||
استراتژیهای زیادی وجود دارند که راهحلی تقریبی برای مسئله راهزن زمینهای ارائه میدهند و میتوان آنها را در دو دسته کلی به تفصیل در زیر قرار داد. |
|||
==== راهزنان خطی آنلاین ==== |
|||
* '''الگوریتم LinUCB ''(محدوده اطمینان بالا)''''' : نویسندگان یک وابستگی خطی بین پاداش مورد انتظار یک عمل و زمینه آن فرض میکنند و فضای نمایش را با استفاده از مجموعهای از پیشبینیکنندههای خطی مدل میکنند. <ref name="lcls10linucb"> |
|||
{{Citation|last=Lihong Li|last2=Wei Chu|last3=John Langford|last4=Robert E. Schapire|title=A contextual-bandit approach to personalized news article recommendation|journal=Proceedings of the 19th International Conference on World Wide Web (WWW 2010)|pages=661–670|year=2010|doi=10.1145/1772690.1772758|arxiv=1003.0146|bibcode=2010arXiv1003.0146L|isbn=9781605587998}} |
|||
</ref> <ref name="clrs11linucb"> |
|||
{{Citation|last=Wei Chu|last2=Lihong Li|last3=Lev Reyzin|last4=Robert E. Schapire|title=Contextual bandits with linear payoff functions|journal=Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS)|pages=208–214|year=2011|url=http://proceedings.mlr.press/v15/chu11a/chu11a.pdf}} |
|||
</ref> |
|||
* '''الگوریتم LinRel (یادگیری تقویتی انجمنی خطی)''' : شبیه LinUCB است، اما از [[تجزیه مقدارهای منفرد|تجزیه ارزش]] تکی به جای رگرسیون Ridge برای به دست آوردن تخمینی از اطمینان استفاده میکند. |
|||
* '''HLINUCBC (LINUCB تاریخی با خوشهها)''' : پیشنهاد شده در مقاله، ایده LinUCB را با اطلاعات تاریخی و خوشهبندی گسترش میدهد. |
|||
==== راهزنان غیر خطی آنلاین ==== |
|||
* '''الگوریتم UCBogram''' : توابع پاداش غیرخطی با استفاده از یک برآوردگر ثابت تکه ای به نام ''رگرسیون'' در رگرسیون ناپارامتریک تخمین زده میشوند. سپس، UCB روی هر قطعه ثابت استفاده میشود. اصلاحات متوالی پارتیشن فضای زمینه به صورت تطبیقی برنامه ریزی یا انتخاب میشوند. <ref name="RigZee10"> |
|||
{{Citation|last=Rigollet|first=Philippe|last2=Zeevi|first2=Assaf|series=Conference on Learning Theory, COLT 2010|title=Nonparametric Bandits with Covariates|year=2010|bibcode=2010arXiv1003.1630R|arxiv=1003.1630}} |
|||
</ref> <ref name="slivkins11"> |
|||
{{Citation|last=Slivkins|first=Aleksandrs|series=Conference on Learning Theory, COLT 2011|title=Contextual bandits with similarity information.|year=2011|url=http://www.jmlr.org/papers/volume15/slivkins14a/slivkins14a.pdf}} |
|||
</ref> <ref name="PerRig13"> |
|||
{{Citation|last=Perchet|first=Vianney|last2=Rigollet|first2=Philippe|journal=[[Annals of Statistics]]|title=The multi-armed bandit problem with covariates|volume=41|number=2|year=2013|doi=10.1214/13-aos1101|pages=693–721|arxiv=1110.6084}} |
|||
</ref> |
|||
* '''الگوریتمهای خطی تعمیمیافته''' : توزیع پاداش از یک مدل خطی تعمیمیافته پیروی میکند، توسعهای برای راهزنهای خطی. <ref name="fcgs10glm"> |
|||
{{Citation|last=Sarah Filippi|last2=Olivier Cappé|last3=Aurélien Garivier|last4=Csaba Szepesvári|title=Parametric Bandits: The Generalized Linear Case|journal=Advances in Neural Information Processing Systems 23 (NIPS)|pages=586–594|year=2010|volume=23|publisher=Curran Associates|url=http://papers.nips.cc/paper/4166-parametric-bandits-the-generalized-linear-case}} |
|||
</ref> <ref name="llz17glm"> |
|||
{{Citation|last=Lihong Li|last2=Yu Lu|last3=Dengyong Zhou|title=Provably optimal algorithms for generalized linear contextual bandits|journal=Proceedings of the 34th International Conference on Machine Learning (ICML)|pages=2071–2080|year=2017|arxiv=1703.00048|bibcode=2017arXiv170300048L|url=http://proceedings.mlr.press/v70/li17c.html}} |
|||
</ref> <ref name="jbnw17glm"> |
|||
{{Citation|last=Kwang-Sung Jun|last2=Aniruddha Bhargava|last3=Robert D. Nowak|last4=Rebecca Willett|title=Scalable generalized linear bandits: Online computation and hashing|journal=Advances in Neural Information Processing Systems 30 (NIPS)|pages=99–109|year=2017|volume=30|publisher=Curran Associates|arxiv=1706.00136|bibcode=2017arXiv170600136J|url=http://papers.nips.cc/paper/6615-scalable-generalized-linear-bandits-online-computation-and-hashing}} |
|||
</ref> <ref name="kzslgb19glm"> |
|||
{{Citation|last=Branislav Kveton|last2=Manzil Zaheer|last3=Csaba Szepesvári|last4=Lihong Li|last5=Mohammad Ghavamzadeh|last6=Craig Boutilier|title=Randomized exploration in generalized linear bandits|journal=Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS)|year=2020|arxiv=1906.08947|bibcode=2019arXiv190608947K}} |
|||
</ref> |
|||
* '''الگوریتم NeuralBandit''' : در این الگوریتم چندین شبکه عصبی برای مدلسازی ارزش پاداشها با دانستن زمینه آموزش داده میشوند و از یک رویکرد چند متخصص برای انتخاب آنلاین پارامترهای پرسپترونهای چند لایه استفاده میکنند. <ref name="Robin2014"> |
|||
{{Citation|last=Allesiardo|first=Robin|last2=Féraud|first2=Raphaël|last3=Djallel|first3=Bouneffouf|contribution=A Neural Networks Committee for the Contextual Bandit Problem|pages=374–381|publisher=Springer|series=[[Lecture Notes in Computer Science]]|title=Neural Information Processing – 21st International Conference, ICONIP 2014, Malaisia, November 03-06,2014, Proceedings|volume=8834|year=2014|isbn=978-3-319-12636-4|doi=10.1007/978-3-319-12637-1_47|arxiv=1409.8191}} |
|||
</ref> |
|||
* '''الگوریتم KernelUCB''' : یک نسخه غیرخطی هستهای از linearUCB، با پیادهسازی کارآمد و تحلیل زمان محدود. <ref name="Valko2014"> |
|||
{{Citation|last=Michal Valko|last2=Nathan Korda|last3=Rémi Munos|last4=Ilias Flaounas|last5=Nello Cristianini|series=29th Conference on Uncertainty in Artificial Intelligence (UAI 2013) and (JFPDA 2013).|title=Finite-Time Analysis of Kernelised Contextual Bandits|arxiv=1309.6869|year=2013|bibcode=2013arXiv1309.6869V}} |
|||
</ref> |
|||
* '''الگوریتم جنگل راهزن''' : یک جنگل تصادفی با دانستن توزیع مشترک زمینهها و پاداشها در [[جنگل تصادفی]] ساخته شده و تحلیل میشود. <ref>{{Cite journal|last=Féraud|first=Raphaël|last2=Allesiardo|first2=Robin|last3=Urvoy|first3=Tanguy|last4=Clérot|first4=Fabrice|date=2016|title=Random Forest for the Contextual Bandit Problem|url=http://jmlr.org/proceedings/papers/v51/feraud16.html|journal=Aistats|pages=93–101}}</ref> |
|||
* '''الگوریتم مبتنی بر اوراکل''' : این الگوریتم مسئله راهزن زمینه ای را به یک سری مسائل یادگیری نظارت شده کاهش میدهد و بر فرض تحقق پذیری معمولی در تابع پاداش متکی نیست. <ref name="minimonster"> |
|||
{{Citation|last=Alekh Agarwal|last2=Daniel J. Hsu|last3=Satyen Kale|last4=John Langford|last5=Lihong Li|last6=Robert E. Schapire|title=Taming the monster: A fast and simple algorithm for contextual bandits|journal=Proceedings of the 31st International Conference on Machine Learning (ICML)|pages=1638–1646|year=2014|arxiv=1402.0555|bibcode=2014arXiv1402.0555A|url=http://proceedings.mlr.press/v32/agarwalb14.html}} |
|||
</ref> |
|||
=== راهزن زمینهای محدود === |
|||
* '''راهزنان توجه زمینهای یا راهزن زمینهای با زمینه محدود''' : <ref>Contextual Bandit with Restricted Context, Djallel Bouneffouf, 2017 <https://www.ijcai.org/Proceedings/2017/0203.pdf></ref> نویسندگان فرمول جدیدی از مدل راهزن چند دست را در نظر میگیرند، که راهزن زمینهای با زمینه محدود نامیده میشود، که در آن تنها تعداد محدودی از ویژگیها توسط آموزنده قابل دسترسی است. هر تکرار این فرمول جدید ناشی از مسائل آنلاین مختلف است که در آزمایشهای بالینی، سیستمهای توصیهکننده و مدلسازی توجه به وجود میآیند. در اینجا، آنها الگوریتم راهزن استاندارد چند دستی معروف به نمونهبرداری تامپسون را برای استفاده از تنظیمات زمینه محدود تطبیق میدهند و دو الگوریتم جدید به نامهای نمونهبرداری تامپسون با زمینه محدود (TSRC) و نمونهبرداری تامپسون ویندوز با زمینه محدود (WTSRC) را پیشنهاد میکنند. ، به ترتیب برای جابجایی محیطهای ثابت و غیر ثابت. |
|||
در عمل، معمولاً هزینه ای مرتبط با منابع مصرف شده توسط هر اقدام وجود دارد و هزینه کل توسط بودجه در بسیاری از کاربردها مانند جمع سپاری و آزمایشهای بالینی محدود میشود. راهزن زمینهای محدود (CCB) چنین مدلی است که هم محدودیتهای زمانی و هم بودجه را در یک محیط راهزن چند دست در نظر میگیرد. A. Badanidiyuru و همکاران. <ref name="Badanidiyuru2014COLT"> |
|||
{{Citation|last=Badanidiyuru|first=A.|last2=Langford|first2=J.|last3=Slivkins|first3=A.|title=Proceeding of Conference on Learning Theory (COLT)|chapter=Resourceful contextual bandits|year=2014|chapter-url=http://www.jmlr.org/proceedings/papers/v35/badanidiyuru14.pdf}} |
|||
</ref> ابتدا راهزنهای زمینهای را با محدودیتهای بودجه مورد مطالعه قرار داد، که به آنها راهزنهای زمینهای منبع نیز میگویند و نشان داد که <math>O(\sqrt{T})</math> پشیمانی دست یافتنی است با این حال، کار آنها بر روی مجموعه محدودی از سیاستها متمرکز است و الگوریتم از نظر محاسباتی ناکارآمد است. |
|||
[[پرونده:Framework_of_UCB-ALP_for_Constrained_Contextual_Bandits.jpg|بندانگشتی| چارچوب UCB-ALP برای راهزنان زمینهای محدود]] |
|||
یک الگوریتم ساده با پشیمانی لگاریتمی در موارد زیر پیشنهاد شده است: <ref name="Wu2015UCBALP"> |
|||
{{Citation|url=https://papers.nips.cc/paper/6008-algorithms-with-logarithmic-or-sublinear-regret-for-constrained-contextual-bandits|last=Wu|first=Huasen|last2=Srikant|first2=R.|last3=Liu|first3=Xin|last4=Jiang|first4=Chong|title=Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits|journal=The 29th Annual Conference on Neural Information Processing Systems (NIPS)|pages=433–441|year=2015|volume=28|publisher=Curran Associates|bibcode=2015arXiv150406937W|arxiv=1504.06937}} |
|||
</ref> |
|||
== جستارهای وابسته == |
|||
* شاخص گیتینز - یک استراتژی قدرتمند و کلی برای بررسی مسئله راهزن. |
|||
* [[الگوریتم حریصانه|الگوریتم حریص]] |
|||
* توقف بهینه |
|||
* نظریه جستجو |
|||
* برنامه ریزی تصادفی |
|||
[[رده:یادگیری ماشینی]] |
[[رده:یادگیری ماشینی]] |
||
[[رده:یادگیری تقویتی]] |
نسخهٔ ۳۰ ژانویهٔ ۲۰۲۳، ساعت ۱۷:۵۰
در تئوری احتمالات و یادگیری ماشین ، مسئله راهزن چند دست مسئلهای است که در آن مجموعه محدود ثابتی از منابع باید بین گزینههای رقیب تخصیص داده شود. انتخابها به گونهای که سود مورد انتظار آنها را به حداکثر برساند، زمانی که ویژگیهای هر انتخاب در زمان تخصیص فقط تا حدی شناخته شده است و ممکن است با گذشت زمان یا با تخصیص منابع به آن انتخاب، بهتر شناخته شود. </ref> این یک مسئله کلاسیک یادگیری تقویتی است که مسئله معاوضه اکتشاف – بهره برداری را توصیف میزند. این نام از تصور یک قمارباز در ردیف دستگاههای بازی گرفته شده است، که باید تصمیم بگیرد که با کدام دستگاهها بازی کند، هر دستگاه را چند مرتبه بازی کند و به چه ترتیبی بازی کند، و آیا با دستگاه فعلی ادامه دهد یا دستگاه دیگری را امتحان کند. [۱] مسئله راهزن چند دست در دستهبندی برنامه ریزی تصادفی قرار میگیرد.
در این مسئله، هر دستگاه یک پاداش تصادفی را از یک توزیع احتمال خاص برای آن دستگاه ارائه میکند، که این توزیع از قبل مشخص نیست. هدف قمارباز به حداکثر رساندن مجموع پاداشهای به دست آمده از طریق دنبالهای از کشیدن اهرمها است. [۲] [۳] معاوضه اساسیای که قمارباز در هر آزمایشی با آن روبرو میشود، بین «استثمار» از دستگاهی است که بالاترین بازدهی مورد انتظار را دارد و «اکتشاف» برای به دست آوردن اطلاعات بیشتر در مورد بازدهی مورد انتظار دستگاههای دیگر است. مبادله بین اکتشاف و بهرهبرداری در یادگیری ماشین بررسی شده است. در عمل، راهزن چند دست برای مدلسازی مسائلی مانند مدیریت پروژههای تحقیقاتی در یک سازمان بزرگ، مانند یک بنیاد علمی یا یک شرکت داروسازی، استفاده شده است. [۲] [۳] در نسخههای اولیه مسئله، قمارباز بدون هیچ دانش اولیه در مورد دستگاهها شروع میکند.
هربرت رابینز در سال 1952، با درک اهمیت مسئله، استراتژیهای انتخاب جمعیت همگرا را در "برخی از جنبههای طراحی متوالی آزمایشها" ساخت. [۴] یک قضیه، شاخص گیتینز ، که برای اولین بار توسط جان سی منتشر شد، یک سیاست بهینه برای به حداکثر رساندن پاداش مورد انتظار ارائه میدهد. [۵]
انگیزه تجربی
مسئله راهزن چند دست، عاملی را مدل میکند که به طور همزمان تلاش میکند دانش جدیدی («اکتشاف») به دست آورد و تصمیمات خود را بر اساس دانش موجود («استثمار») بهینه کند. عامل تلاش میکند تا این دو وظیفه رقابتی را متعادل کند تا ارزش کلی آنها را در بازه زمانی در نظر گرفته شده به حداکثر برساند. کاربردهای عملی زیادی از مسئله راهزن وجود دارد، به عنوان نمونه:
- کارآزماییهای بالینی که اثرات درمانهای تجربی مختلف را در عین به حداقل رساندن تلفات بیمار بررسی میکنند، [۲] [۳] [۶] [۷]
- تلاشهای مسیریابی تطبیقی برای به حداقل رساندن تاخیر در شبکه،
- طراحی سبد مالی [۸] [۹]
در این مثالهای عملی، مسئله مستلزم رسیدن به حداکثر پاداش بر اساس دانشی است که قبلاً به دست آوردهایم و تلاش برای اقدامات جدید برای افزایش بیشتر دانش است. این به عنوان معاوضه بهره برداری در مقابل اکتشاف در یادگیری ماشینی شناخته میشود.
این مدل برای کنترل تخصیص پویای منابع به پروژههای مختلف استفاده شده است و به این سؤال پاسخ میدهد که با توجه به عدم اطمینان در مورد دشواری و بازدهی هر گزینه، روی کدام پروژه کار شود. [۱۰]
این مسئله در ابتدا توسط دانشمندان متفقین در جنگ جهانی دوم مورد توجه قرار گرفت، اما به قدری غیرقابل حل بود که به گفته پیتر ویتل ، پیشنهاد شد که این مسئله در بین آلمانیها رها شود تا دانشمندان آلمانی نیز بتوانند وقت خود را برای آن تلف کنند. [۱۱]
نسخهای از مسئله که اکنون معمولاً مورد بررسی قرار میگیرد توسط هربرت رابینز در سال 1952 فرموله شده است.
مدل راهزن چند دستی
راهزن چند دستی (کوتاه: MAB) را میتوان به عنوان مجموعه ای از توزیعهای واقعی دید. ، هر توزیع با پاداشهای ارائه شده توسط یکی از اهرم مرتبط است. اگر مقادیر میانگین مرتبط با این توزیعهای پاداش باشد، قمارباز به طور مکرر در هر دور یک اهرم بازی میکند و پاداش مربوطه را مشاهده میکند. هدف این است که مجموع پاداشهای جمع آوری شده را به حداکثر برساند. افق تعداد دورهایی است که باید انجام شود. مسئله راهزن به طور رسمی معادل فرآیند تصمیم گیری مارکوف یک حالته است. پشیمانی بعد از دور به عنوان تفاوت مورد انتظار بین مجموع پاداش مرتبط با یک استراتژی بهینه و مجموع پاداشهای جمع آوری شده تعریف میشود:
،
جایی که حداکثر میانگین پاداش است، ، و پاداش در دور t است.
استراتژی صفر پشیمانی استراتژی است که میانگین پشیمانی آن در هر راند وقتی تعداد دورهای بازی شده به بی نهایت میل میکند با احتمال 1 به صفر میل میکند. به طور شهودی، استراتژیهای بدون پشیمانی تضمین میشوند که اگر راندهای کافی بازی شوند، به یک استراتژی بهینه (الزاماً منحصربهفرد) همگرا میشوند.
تغییرات
یک فرمول متداول، راهزن چند دست دودویی یا راهزن چند دست برنولی است که یک جایزه با احتمال صادر میکند و در غیر این صورت پاداش صفر است.
فرمول دیگری از راهزن چند دشت دارای هر اهرم نشان دهنده یک ماشین مارکوف مستقل است. هر بار که دستگاه خاصی بازی میشود، وضعیت آن دستگاه به دستگاه جدیدی میرود که بر اساس احتمالات تکامل حالت مارکوف انتخاب میشود. بسته به وضعیت فعلی دستگاه یک پاداش وجود دارد. در یک تعمیم به نام "مسئله راهزن بیقرار"، حالتهای دستگاههای بازی نشده نیز می تواند در طول زمان تکامل یابد. [۱۲] همچنین در مورد سیستمهایی که تعداد انتخابها (در مورد اینکه کدام دستگاه بازی شود) در طول زمان افزایش مییابد، بحث شده است. [۱۳]
محققان علوم کامپیوتر راهزنان چند دست را تحت بدترین مفروضات (worst-case) مورد مطالعه قرار دادهاند و الگوریتمهایی را برای به حداقل رساندن پشیمانی در زمانی متناهی و نامتناهی برای بازدهی اهرمهای تصادفی [۱۴] و غیر تصادفی [۱۵] به دست آوردهاند.
استراتژیهای راهزن
یک پیشرفت بزرگ، ایجاد استراتژیها یا سیاستهای انتخاب بهینه جمعیت (که دارای حداکثر نرخ همگرایی یکنواخت با جمعیت با بالاترین میانگین هستند) در کار شرح داده شده در زیر است.
راه حلهای بهینه
در مقاله "قوانین تخصیص تطبیقی کارآمد مجانبی"، لای و رابینز [۱۶] (به دنبال مقالات رابینز و همکارانش که به رابینز در سال 1952 بازمیگردند) سیاستهای انتخاب جمعیت همگرا را ارائه کردند که سریعترین نرخ همگرایی را (به جمعیت با بالاترین میانگین) برای حالتی که توزیع پاداش جمعیت خانواده نمایی یک پارامتری است، دارد. سپس در کاتهاکیس و رابینز [۱۷] سادهسازی خطمشی و اثبات اصلی برای مورد جمعیتهای عادی با واریانسهای شناخته شده ارائه شد. پیشرفت قابل توجه بعدی توسط Burnetas و Katehakis در مقاله "سیاستهای تطبیقی بهینه برای مسائل تخصیص متوالی"، [۱۸] به دست آمد، جایی که سیاستهای مبتنی بر شاخص با حداکثر نرخ همگرایی یکنواخت، تحت شرایط عمومی تر که شامل مواردی است که در آن توزیعها وجود دارد، ساخته شد. نتایج هر جمعیت به بردار پارامترهای ناشناخته بستگی دارد. Burnetas و Katehakis همچنین یک راه حل صریح برای مورد مهمی ارائه کردند که در آن توزیع نتایج از توزیعهای گسسته و تکمتغیره دلخواه (یعنی ناپارامتریک) پیروی میکند.
بعداً در «سیاستهای تطبیقی بهینه برای فرآیندهای تصمیم مارکوف» [۱۹] بورنتاس و کاتهاکیس مدل بسیار بزرگتری از فرآیندهای تصمیمگیری مارکوف را تحت اطلاعات محدود مطالعه کردند، جایی که قانون گذار و/یا پاداش یک دوره ممکن است به پارامترهای ناشناخته بستگی داشته باشد. در این کار، نویسندگان یک فرم صریح برای یک کلاس از سیاستهای تطبیقی با ویژگیهای نرخ همگرایی حداکثری یکنواخت برای کل پاداش افق محدود مورد انتظار تحت مفروضات کافی فضاهای کنش حالت محدود و کاهشناپذیری قانون گذار ارائه کردند. یکی از ویژگیهای اصلی این سیاستها این است که انتخاب اقدامات، در هر حالت و دوره زمانی، بر اساس شاخصهایی است که تورمهای سمت راست معادلات میانگین تخمینی بهینه پاداش هستند. این تورمها اخیراً در کار تواری و بارتلت، [۲۰] اورتنر [۲۱] فیلیپی، کاپی، و گاریویه [۲۲] و هوندا و تاکمورا، رویکرد خوشبینانه نامیده میشوند. [۲۳]
برای راهزنان چند دست برنولی، پیلارسکی و همکاران روشهای محاسباتی استخراج راهحلهای کاملاً بهینه (نه فقط مجانبی) را با استفاده از برنامهنویسی پویا در مقاله "سیاست بهینه برای راهزنان برنولی: محاسبات و الگوریتم" مطالعه کردند. [۲۴] این کار از طریق طرحهای نمایهسازی، جداول جستجو و سایر تکنیکها، راهحلهای بهینه عملاً قابل اجرا را برای راهزنان برنولی ارائه کرد، مشروط بر اینکه افقهای زمانی و تعداد اهرمها بیش از حد بزرگ نشوند. پیلارسکی و همکاران بعداً این کار را در "پاداش تاخیری راهزنان برنولی: سیاست بهینه و متاالگوریتم پیش بینی کننده PARDI" [۲۵] گسترش داد تا روشی برای تعیین خط مشی بهینه راهزنان برنولی ایجاد کند، زمانی که پاداش ممکن است بلافاصله پس از یک تصمیم آشکار نشود و ممکن است به تاخیر بیفتد. این روش بر محاسبه مقادیر مورد انتظار نتایج پاداش که هنوز آشکار نشده اند و بهروزرسانی توزیع احتمالات پسین هنگام آشکار شدن پاداشها متکی است.
میتوان راه حلهای بهینه برای راهزن چند دست [۲۶] برای استخراج ارزش انتخابهای حیوانات استفاده کرد. فعالیت نورونها در آمیگدال و جسم مخطط شکمی مقادیر به دست آمده از این سیاستها را رمزگذاری میکند و میتواند برای رمزگشایی زمانی که حیوانات انتخابهای اکتشافی در مقابل استثماری انجام دهند استفاده شود. علاوه بر این، سیاستهای بهینه رفتار انتخاب حیوانات را بهتر از استراتژیهای جایگزین پیشبینی میکنند (که در زیر توضیح داده شده است). این نشان میدهد که راهحلهای بهینه برای مسئله راهزن چند دست از نظر بیولوژیکی قابل قبول هستند. [۲۷]
- UCBC (محدودههای بالای اطمینان تاریخی با خوشهها): الگوریتم UCB را برای یک تنظیم جدید به گونه ای تطبیق میدهد که بتواند هم خوشه بندی و هم اطلاعات تاریخی را در خود جای دهد. این الگوریتم مشاهدات تاریخی را با استفاده از هر دو در محاسبه پاداش میانگین مشاهده شده و عبارت عدم قطعیت ترکیب میکند. این الگوریتم اطلاعات خوشهبندی را با بازی در دو سطح ترکیب میکند: ابتدا انتخاب یک خوشه با استفاده از یک استراتژی شبیه به UCB در هر مرحله زمانی، و متعاقبا انتخاب یک اهرم از درون خوشه، دوباره با استفاده از یک استراتژی مشابه UCB.
راه حلهای تقریبی
راهبردهای زیادی وجود دارند که راه حل تقریبی برای مسئله راهزن ارائه میدهند و میتوان آنها را در چهار گروه کلی که در زیر شرح داده شده است قرار داد:
استراتژیهای نیمه یکنواخت
استراتژیهای نیمه یکنواخت اولین (و سادهترین) استراتژیهایی بودند که برای حل تقریبی مسئله راهزن کشف شدند. همه آن استراتژیها رفتار حریصانهای دارند که در آن بهترین اهرم (بر اساس مشاهدات قبلی) همیشه کشیده میشود، مگر زمانی که یک اقدام تصادفی (یکنواخت) انجام شود.
- استراتژی اپسیلون حریص : [۲۸] بهترین اهرم برای نسبت از آزمایشها انتخاب میشود، و یک اهرم به طور تصادفی (با احتمال یکنواخت) برای یک نسبت انتخاب میشود. یک مقدار پارامتر متداول ممکن است باشد، اما بسته به شرایط و تمایلات میتواند بسیار متفاوت باشد.
- استراتژی اپسیلون اول[نیازمند منبع] : مرحله اکتشاف خالص با مرحله بهره برداری خالص دنبال میشود. برای آزمایش در مجموع، مرحله اکتشاف آزمایشها را اشغال میکند و مرحله بهره برداری آزمایش. در طول مرحله اکتشاف، یک اهرم به طور تصادفی انتخاب میشود (با احتمال یکنواخت). در طول مرحله بهره برداری، بهترین اهرم همیشه انتخاب میشود.
- استراتژی کاهش اپسیلون[نیازمند منبع] : شبیه به استراتژی 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 و همکاران. [۵۱] ابتدا راهزنهای زمینهای را با محدودیتهای بودجه مورد مطالعه قرار داد، که به آنها راهزنهای زمینهای منبع نیز میگویند و نشان داد که پشیمانی دست یافتنی است با این حال، کار آنها بر روی مجموعه محدودی از سیاستها متمرکز است و الگوریتم از نظر محاسباتی ناکارآمد است.
یک الگوریتم ساده با پشیمانی لگاریتمی در موارد زیر پیشنهاد شده است: [۵۲]
جستارهای وابسته
- شاخص گیتینز - یک استراتژی قدرتمند و کلی برای بررسی مسئله راهزن.
- الگوریتم حریص
- توقف بهینه
- نظریه جستجو
- برنامه ریزی تصادفی
- ↑ Weber, Richard (1992), "On the Gittins index for multiarmed bandits", Annals of Applied Probability, 2 (4): 1024–1033, doi:10.1214/aoap/1177005588, JSTOR 2959678
- ↑ ۲٫۰ ۲٫۱ ۲٫۲ Gittins, J. C. (1989), Multi-armed bandit allocation indices, Wiley-Interscience Series in Systems and Optimization., Chichester: John Wiley & Sons, Ltd., ISBN 978-0-471-92059-5Gittins, J. C. (1989), Multi-armed bandit allocation indices, Wiley-Interscience Series in Systems and Optimization., Chichester: John Wiley & Sons, Ltd., ISBN 978-0-471-92059-5
- ↑ ۳٫۰ ۳٫۱ ۳٫۲ Berry, Donald A.; Fristedt, Bert (1985), Bandit problems: Sequential allocation of experiments, Monographs on Statistics and Applied Probability, London: Chapman & Hall, ISBN 978-0-412-24810-8Berry, Donald A.; Fristedt, Bert (1985), Bandit problems: Sequential allocation of experiments, Monographs on Statistics and Applied Probability, London: Chapman & Hall, ISBN 978-0-412-24810-8
- ↑ Robbins, H. (1952). "Some aspects of the sequential design of experiments". Bulletin of the American Mathematical Society. 58 (5): 527–535. doi:10.1090/S0002-9904-1952-09620-8.
- ↑ J. C. Gittins (1979). "Bandit Processes and Dynamic Allocation Indices". Journal of the Royal Statistical Society. Series B (Methodological). 41 (2): 148–177. doi:10.1111/j.2517-6161.1979.tb01068.x. JSTOR 2985029.
- ↑ Press, William H. (2009), "Bandit solutions provide unified ethical models for randomized clinical trials and comparative effectiveness research", Proceedings of the National Academy of Sciences, 106 (52): 22387–22392, Bibcode:2009PNAS..10622387P, doi:10.1073/pnas.0912378106, PMC 2793317, PMID 20018711.
- ↑ Press (1986)
- ↑ Brochu, Eric; Hoffman, Matthew W.; de Freitas, Nando (September 2010), Portfolio Allocation for Bayesian Optimization, arXiv:1009.5419, Bibcode:2010arXiv1009.5419B
- ↑ Shen, Weiwei; Wang, Jun; Jiang, Yu-Gang; Zha, Hongyuan (2015), "Portfolio Choices with Orthogonal Bandit Learning", Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI2015)
- ↑ Farias, Vivek F; Ritesh, Madan (2011), "The irrevocable multiarmed bandit problem", Operations Research, 59 (2): 383–399, doi:10.1287/opre.1100.0891
- ↑ Whittle, Peter (1979), "Discussion of Dr Gittins' paper", Journal of the Royal Statistical Society, Series B, 41 (2): 148–177, doi:10.1111/j.2517-6161.1979.tb01069.x
- ↑ Whittle, Peter (1988), "Restless bandits: Activity allocation in a changing world", Journal of Applied Probability, 25A: 287–298, doi:10.2307/3214163, JSTOR 3214163, MR 0974588
- ↑ Whittle, Peter (1981), "Arm-acquiring bandits", Annals of Probability, 9 (2): 284–292, doi:10.1214/aop/1176994469
- ↑ Auer, P.; Cesa-Bianchi, N.; Fischer, P. (2002). "Finite-time Analysis of the Multiarmed Bandit Problem". Machine Learning. 47 (2/3): 235–256. doi:10.1023/A:1013689704352.
- ↑ Auer, P.; Cesa-Bianchi, N.; Freund, Y.; Schapire, R. E. (2002). "The Nonstochastic Multiarmed Bandit Problem". SIAM J. Comput. 32 (1): 48–77. CiteSeerX 10.1.1.130.158. doi:10.1137/S0097539701398375.
- ↑ Lai, T.L.; Robbins, H. (1985). "Asymptotically efficient adaptive allocation rules". Advances in Applied Mathematics. 6 (1): 4–22. doi:10.1016/0196-8858(85)90002-8.
- ↑ Katehakis, M.N.; Robbins, H. (1995). "Sequential choice from several populations". Proceedings of the National Academy of Sciences of the United States of America. 92 (19): 8584–5. Bibcode:1995PNAS...92.8584K. doi:10.1073/pnas.92.19.8584. PMC 41010. PMID 11607577.
- ↑ Burnetas, A.N.; Katehakis, M.N. (1996). "Optimal adaptive policies for sequential allocation problems". Advances in Applied Mathematics. 17 (2): 122–142. doi:10.1006/aama.1996.0007.
- ↑ Burnetas, A.N.; Katehakis, M.N. (1997). "Optimal adaptive policies for Markov decision processes". Math. Oper. Res. 22 (1): 222–255. doi:10.1287/moor.22.1.222.
- ↑ Tewari, A.; Bartlett, P.L. (2008). "Optimistic linear programming gives logarithmic regret for irreducible MDPs" (PDF). Advances in Neural Information Processing Systems. 20. CiteSeerX 10.1.1.69.5482.
- ↑ Ortner, R. (2010). "Online regret bounds for Markov decision processes with deterministic transitions". Theoretical Computer Science. 411 (29): 2684–2695. doi:10.1016/j.tcs.2010.04.005.
- ↑ Filippi, S. and Cappé, O. and Garivier, A. (2010). "Online regret bounds for Markov decision processes with deterministic transitions", Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, pp. 115–122
- ↑ Honda, J.; Takemura, A. (2011). "An asymptotically optimal policy for finite support models in the multi-armed bandit problem". Machine Learning. 85 (3): 361–391. arXiv:0905.2776. doi:10.1007/s10994-011-5257-4.
- ↑ Pilarski, Sebastian; Pilarski, Slawomir; Varró, Dániel (February 2021). "Optimal Policy for Bernoulli Bandits: Computation and Algorithm Gauge". IEEE Transactions on Artificial Intelligence. 2 (1): 2–17. doi:10.1109/TAI.2021.3074122. ISSN 2691-4581.
- ↑ Pilarski, Sebastian; Pilarski, Slawomir; Varro, Daniel (2021). "Delayed Reward Bernoulli Bandits: Optimal Policy and Predictive Meta-Algorithm PARDI". IEEE Transactions on Artificial Intelligence. 3 (2): 152–163. doi:10.1109/TAI.2021.3117743. ISSN 2691-4581.
- ↑ Averbeck, B.B. (2015). "Theory of choice in bandit, information sampling, and foraging tasks". PLOS Computational Biology. 11 (3): e1004164. Bibcode:2015PLSCB..11E4164A. doi:10.1371/journal.pcbi.1004164. PMC 4376795. PMID 25815510.
- ↑ Costa, V.D.; Averbeck, B.B. (2019). "Subcortical Substrates of Explore-Exploit Decisions in Primates". Neuron. 103 (3): 533–535. doi:10.1016/j.neuron.2019.05.017. PMC 6687547. PMID 31196672.
- ↑ Sutton, R. S. & Barto, A. G. 1998 Reinforcement learning: an introduction. Cambridge, MA: MIT Press.
- ↑ Tokic, Michel (2010), "Adaptive ε-greedy exploration in reinforcement learning based on value differences" (PDF), KI 2010: Advances in Artificial Intelligence, Lecture Notes in Computer Science, vol. 6359, Springer-Verlag, pp. 203–210, doi:10.1007/978-3-642-16111-7_23, ISBN 978-3-642-16110-0.
- ↑ Tokic, Michel; Palm, Günther (2011), "Value-Difference Based Exploration: Adaptive Control Between Epsilon-Greedy and Softmax" (PDF), KI 2011: Advances in Artificial Intelligence, Lecture Notes in Computer Science, vol. 7006, Springer-Verlag, pp. 335–346, ISBN 978-3-642-24455-1.
- ↑ Gimelfarb, Michel; Sanner, Scott; Lee, Chi-Guhn (2019), "ε-BMC: A Bayesian Ensemble Approach to Epsilon-Greedy Exploration in Model-Free Reinforcement Learning" (PDF), Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, AUAI Press, p. 162.
- ↑ Bouneffouf, D.; Bouzeghoub, A.; Gançarski, A. L. (2012), "A Contextual-Bandit Algorithm for Mobile Context-Aware Recommender System", Neural Information Processing, Lecture Notes in Computer Science, vol. 7665, p. 324, doi:10.1007/978-3-642-34487-9_40, ISBN 978-3-642-34486-2
- ↑ Scott, S.L. (2010), "A modern Bayesian look at the multi-armed bandit", Applied Stochastic Models in Business and Industry, 26 (2): 639–658, doi:10.1002/asmb.874
- ↑ Olivier Chapelle; Lihong Li (2011), "An empirical evaluation of Thompson sampling", Advances in Neural Information Processing Systems 24 (NIPS), Curran Associates, 24: 2249–2257
- ↑ Vermorel, Joannes; Mohri, Mehryar (2005), Multi-armed bandit algorithms and empirical evaluation (PDF), In European Conference on Machine Learning, Springer, pp. 437–448Vermorel, Joannes; Mohri, Mehryar (2005), Multi-armed bandit algorithms and empirical evaluation (PDF), In European Conference on Machine Learning, Springer, pp. 437–448
- ↑ Langford, John; Zhang, Tong (2008), "The Epoch-Greedy Algorithm for Contextual Multi-armed Bandits", Advances in Neural Information Processing Systems 20, vol. 20, Curran Associates, Inc., pp. 817–824
- ↑ Lihong Li; Wei Chu; John Langford; Robert E. Schapire (2010), "A contextual-bandit approach to personalized news article recommendation", Proceedings of the 19th International Conference on World Wide Web (WWW 2010): 661–670, arXiv:1003.0146, Bibcode:2010arXiv1003.0146L, doi:10.1145/1772690.1772758, ISBN 9781605587998
- ↑ Wei Chu; Lihong Li; Lev Reyzin; Robert E. Schapire (2011), "Contextual bandits with linear payoff functions" (PDF), Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS): 208–214
- ↑ Rigollet, Philippe; Zeevi, Assaf (2010), Nonparametric Bandits with Covariates, Conference on Learning Theory, COLT 2010, arXiv:1003.1630, Bibcode:2010arXiv1003.1630R
- ↑ Slivkins, Aleksandrs (2011), Contextual bandits with similarity information. (PDF), Conference on Learning Theory, COLT 2011
- ↑ Perchet, Vianney; Rigollet, Philippe (2013), "The multi-armed bandit problem with covariates", Annals of Statistics, 41 (2): 693–721, arXiv:1110.6084, doi:10.1214/13-aos1101
- ↑ Sarah Filippi; Olivier Cappé; Aurélien Garivier; Csaba Szepesvári (2010), "Parametric Bandits: The Generalized Linear Case", Advances in Neural Information Processing Systems 23 (NIPS), Curran Associates, 23: 586–594
- ↑ Lihong Li; Yu Lu; Dengyong Zhou (2017), "Provably optimal algorithms for generalized linear contextual bandits", Proceedings of the 34th International Conference on Machine Learning (ICML): 2071–2080, arXiv:1703.00048, Bibcode:2017arXiv170300048L
- ↑ Kwang-Sung Jun; Aniruddha Bhargava; Robert D. Nowak; Rebecca Willett (2017), "Scalable generalized linear bandits: Online computation and hashing", Advances in Neural Information Processing Systems 30 (NIPS), Curran Associates, 30: 99–109, arXiv:1706.00136, Bibcode:2017arXiv170600136J
- ↑ Branislav Kveton; Manzil Zaheer; Csaba Szepesvári; Lihong Li; Mohammad Ghavamzadeh; Craig Boutilier (2020), "Randomized exploration in generalized linear bandits", Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), arXiv:1906.08947, Bibcode:2019arXiv190608947K
- ↑ Allesiardo, Robin; Féraud, Raphaël; Djallel, Bouneffouf (2014), "A Neural Networks Committee for the Contextual Bandit Problem", Neural Information Processing – 21st International Conference, ICONIP 2014, Malaisia, November 03-06,2014, Proceedings, Lecture Notes in Computer Science, vol. 8834, Springer, pp. 374–381, arXiv:1409.8191, doi:10.1007/978-3-319-12637-1_47, ISBN 978-3-319-12636-4
- ↑ Michal Valko; Nathan Korda; Rémi Munos; Ilias Flaounas; Nello Cristianini (2013), Finite-Time Analysis of Kernelised Contextual Bandits, 29th Conference on Uncertainty in Artificial Intelligence (UAI 2013) and (JFPDA 2013)., arXiv:1309.6869, Bibcode:2013arXiv1309.6869V
- ↑ Féraud, Raphaël; Allesiardo, Robin; Urvoy, Tanguy; Clérot, Fabrice (2016). "Random Forest for the Contextual Bandit Problem". Aistats: 93–101.
- ↑ Alekh Agarwal; Daniel J. Hsu; Satyen Kale; John Langford; Lihong Li; Robert E. Schapire (2014), "Taming the monster: A fast and simple algorithm for contextual bandits", Proceedings of the 31st International Conference on Machine Learning (ICML): 1638–1646, arXiv:1402.0555, Bibcode:2014arXiv1402.0555A
- ↑ Contextual Bandit with Restricted Context, Djallel Bouneffouf, 2017 <https://www.ijcai.org/Proceedings/2017/0203.pdf>
- ↑ Badanidiyuru, A.; Langford, J.; Slivkins, A. (2014), "Resourceful contextual bandits" (PDF), Proceeding of Conference on Learning Theory (COLT)
- ↑ Wu, Huasen; Srikant, R.; Liu, Xin; Jiang, Chong (2015), "Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits", The 29th Annual Conference on Neural Information Processing Systems (NIPS), Curran Associates, 28: 433–441, arXiv:1504.06937, Bibcode:2015arXiv150406937W