On incremental approximate saddle-point computation in zero-sum matrix games

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