الگوریتمی برای هدایت بازی‌های چندعاملی با بازخورد محدود

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

برای این شرایط، نویسندگان الگوریتم‌هایی از خانوادهٔ «نصف‌کردن» ارائه می‌کنند که در بازی‌های فرم نرمال تفاوت مطلوبیت‌ها و در بازی‌های گسترده تفاوت ارزش ادامهٔ مشروط را می‌آموزند. پیچیدگی نمونهٔ این روش‌ها از مرتبهٔ \(\widetilde O(\varepsilon^{-2})\) است؛ به‌گفتهٔ نویسندگان، این نرخ با کران‌های پایین بدترین‌حالت، جز در عوامل لگاریتمی، مطابقت دارد.

پژوهش سپس این روش‌های یادگیری را با صورت‌بندی لاگرانژی ترکیب می‌کند تا الگوریتم آنلاین «یادگیری–محاسبه–هدایت» شکل بگیرد؛ الگوریتمی که این سه مرحله را درهم می‌آمیزد و عامل‌ها را به‌سوی تعادل‌های هم‌بستهٔ گسترده‌فرمِ بهینه برای میانجی هدایت می‌کند. نویسندگان می‌گویند با احتمال بالا، شکاف مستقیم‌بودن و شکاف بهینگی این الگوریتم از مرتبهٔ \(\widetilde O(T^{-1/4})\) است و میانگین زمانی پرداخت‌ها از مرتبهٔ \(\widetilde O(T^{-1/8})\) باقی می‌ماند. مقاله در arXiv منتشر شده و پیش‌چاپ است.