Çok Kollu Haydut (Multi-Armed Bandit)

Çok Kollu Haydut nedir?

Adı kumarhaneden geliyor: önünde birden fazla kollu bir slot makinesi var, her kol farklı ama bilmediğin bir olasılıkla ödül veriyor. Elinde sınırlı sayıda deneme hakkı var ve toplam kazancını en yükseğe çıkarmak istiyorsun. Sorun şu: hangi kolun en iyi olduğunu önceden bilmiyorsun, öğrenmenin tek yolu çekmek.

Bu ikilem makine öğrenmesinin en temel problemlerinden biri. En iyi kolu bilseydin hep onu çekerdin; ama bilmediğin için denemek zorundasın, denemek de bazen kötü kollara düşmek demek.

Nasıl çalışır?

İki şey arasında sürekli bir denge kurarsın: exploration •keşif — belki daha iyi olan seçenekleri denemek• ve exploitation •sömürü — şu ana kadar bulduğun en iyi seçeneğe yüklenmek•. Çok keşfedersen bildiğin iyi koldan yeterince kazanamazsın; çok sömürürsen çok daha iyi bir kolu hiç fark etmeyebilirsin.

Performansı regret •pişmanlık• ile ölçeriz: her adımda, en iyi stratejiyle senin stratejinin kazancı arasındaki fark. İyi bir yöntem toplam pişmanlığı mümkün olduğunca küçük tutar.

Pratikte birkaç klasik strateji var: epsilon-greedy çoğu zaman en iyi kolu çeker ama küçük bir olasılıkla rastgele dener; UCB (Upper Confidence Bound) az denenmiş kollara bir belirsizlik primi verip onları öne çıkarır; Thompson sampling ise her kol için bir olasılık dağılımı tutup ondan örnekleyerek seçim yapar. Ortak fikir aynı: başta daha çok keşfet, zaman ilerledikçe keşfi yavaşça azalt.

Neden önemli?

Çünkü gerçek hayatta çoğu karar tam da böyle: sonucu önceden bilmeden, deneyerek ve her denemenin bir maliyeti varken seçim yapıyorsun. Problem zor, çünkü nadiren ödül veren bir kol aslında en değerlisi olabilir — onu ayırt etmek çok sayıda deneme ister. Uzun bir zaman ufkun varsa başta daha cömert keşfetmek mantıklı; çünkü bulduğun iyi seçeneğin keyfini sürecek daha çok adımın kalır.

Kullanım alanları

A/B testlerinde hangi versiyonun daha iyi olduğunu trafiği boşa harcamadan bulmak; online reklamda hangi reklamı göstereceğine karar vermek; öneri sistemlerinde yeni içerikle bilinen içerik arasında denge kurmak. reinforcement learning ve Monte Carlo Tree Search gibi daha büyük yöntemlerin de kalbinde bu ikilem yatıyor.