Gelen matematik , daha kesin olarak olasılık teorisi , tek slot sorunu (genellenebilir K-kolunun haydut problem ya da N-kol eşkıya sorunu ) aşağıdaki gibi resim olarak formüle edilir: Bir kullanıcı (bir madde ), slot makineleri bakan, hangi makinelerin oynanacağına karar vermelidir. Her makine, kullanıcının önceden bilmediği ortalama bir ödül verir. Amaç, kullanıcının kümülatif kazancını maksimize etmektir.
Bu, pekiştirmeli öğrenmeye bir örnektir . Tipik olarak, kullanıcının politikası, sömürü (çok şey öğrendiği makineyi kullanmak) ve keşif (daha fazla kazanmayı ummak için başka bir makineyi test etmek) arasında gidip gelir. Tek kollu haydut sorunu, tek devletli bir Markov karar alma süreci olarak görülebilir .
Bu bölümde, Auer ve diğerleri tarafından yazılan makaleden bazı notasyonları alarak sorunu resmileştiriyoruz..
K slot makinelerini düşünün. Sorunun girdisi , tüm 1 ≤ i ≤ K için X i, n rasgele değişkenler ve n ≥ 1 tarafından verilir; burada i indisi, K makinelerinden birini (veya haydutun bir "kolunu") ve indeksi temsil eder. n bir dönüşü temsil eder.Tüm bu rastgele değişkenlerin bağımsız olduğunu ve aynı i makinesinin değişkenlerinin, yani X i, 1 , X i, 2 , vb. değişkenlerinin , aynı bilinmeyen olasılık dağılımını takip ettiğini varsayıyoruz . ajan, beklenti μ i .
Buna karşılık, kullanıcı seçtiği makineye bağlı olarak bir ödül alacak. Tek kollu bir haydutun klasik bir örneği, makinenin p i olasılıkla 1 ve 1-p i olasılıkla 0 ödülünü getirdiği durumdur .
Kullanıcı, en yüksek ortalama ödülü getiren slot makinesini bulmaya çalışır. Penguen problemi için bir politika veya strateji , oynanacak bir sonraki makineyi önceki seçimlere ve elde edilen ödüllere göre seçen bir algoritmadır. Amaç, pişmanlığı en aza indiren , yani en iyi makineyi seçme ile ilgili olarak politikanın ne kaybettiğini ifade eden politikalar sağlamaktır.
Tek kollu bir haydut probleminde, n kez en iyi makineyi kullanmanın ödülü ile politikaya uygun olarak yapılan n denemeden sonra ödül beklentisi arasındaki fark, n denemeden sonra pişmanlık olarak tanımlanır. Resmi olarak, bu pişmanlık şu değere sahiptir:
en iyi makinenin ortalama ödülü nerede ve o anda önerilen strateji ile elde edilen ödülü belirler .
Bu nedenle, tek kollu haydut problemini çözmek için pekiştirmeli öğrenme algoritmaları önerilmiştir.
Haydut algoritması, adını oyuncunun kazancını maksimize etmeye çalıştığı slot makinelerinden ( çok kollu haydut ) alır. 1960'larda klinik deneylerdeki uygulamalar için tanıtıldılar.
Bir haydut algoritmasının ilkesi şu şekilde tanımlanabilir: 2 kaynağımız var A ve B (sırasıyla kullanıldığında pA ve pB'nin tatmin edici olma olasılığına sahip) ve ikisinden hangisinin en verimli olduğunu belirlemek istiyoruz.
Açgözlü bir yaklaşım sadece benimkidir, keşfetmek değil. Böylece, bir makinenin a kolunun değerini (eylem için vardır) şu şekilde hesaplıyoruz:
Açgözlü seçim, maksimize eden eylemlerden birini seçmekten ibarettir . Bu yaklaşımla optimuma ulaşılmaz. Temsilci, ε> 0 olasılıkla keyfi bir eylem seçerse, hesaplanan politikayı geliştirdiğimizi gösteriyoruz. Aşağıdaki algoritma, ε-açgözlü dediğimiz tek kollu haydut problemi için basit bir algoritmadır.
initialiser pour tout bras a: Q(a) := 0 N(a) := 0 boucle pour toujours: avec une probabilité ε: a := un bras au hasard sinon: a := une action qui maximise Q(a) R := récompense obtenue en tirant a N(a) := N(a) + 1 Q(a) := Q(a) + (R - Q(a)) / N(a)Mevcut değerini Q (a) 'da saklıyoruz.
Tze Leung Lai ve Herbert Robbins algoritmaları ödül için belirli ailelerin olasılık dağılımı için bir logaritma fonksiyonu ile sınırlı bir pişmanlık alınmasını sağlarlar öğrenme takviye verdi: . Başka bir deyişle, optimum makinenin diğer makinelere göre üssel olarak daha sık oynandığı anlamına gelir.
Thompson örnekleme algoritması , bu sorunu çözmek için önerilen ilk algoritmadır .
Kullanıcı her seferinde en yüksek indekse sahip makineyi seçer. Bu endeks, bir beta yasasını izleyen rastgele bir değişkendir . Her makine için, kullanıcı , parametreleri ve 1 olarak başlatılan bir beta yasasına göre bir indeks çizer . Kullanıcı makinelerden birini her kullandığında , ödülü alırsa vb .
UCB algoritması ( Üst Güven Sınırları için ) 2002 yılında P. Auer tarafından önerildi. Bu algoritma ile kullanıcı, makinelerin her biri için ödülün deneysel ortalamasını hesaplar.
Bu denklemde, kullanıcı tarafından gerçekleştirilen test sayısı, tayin makinede, kullanıcı tarafından yapılan test sayısı , test sırasında elde edilen bir ödül belirtmektedir . makinenin test için seçildiğini gösteren gösterge işlevini belirler .
Her kanaldaki endeksi hesaplamak için, algoritmanın farklı makineleri keşfetmesine olanak tanıyan bir önyargı ekliyoruz.
Önyargı , pişmanlıkta logaritmik bir düşüşe sahip olacak şekilde seçilmelidir. Önyargı:
pişmanlığı logaritmik bir şekilde sınırlandırmaya izin verir.
Bu algoritmanın birçok iyileştirmesi mevcuttur.
En tipik uygulama bir otomatik satış makinası problem eski ve yeni bir dozaj arasında bir seçim olduğunu aşı veya ilaç yeni ürün kabul veya gerekip gerekmediğini de mümkün olduğu kadar çabuk belirlenmesi gerekmektedir: (ya da iki farklı olanlar) eski olanı sürdürdü. Herhangi bir hata, insan hayatının kaybına (veya en azından, tamamlanmamış tedaviden veya aşırı yan etkilerden kaynaklanan sorunlardan muzdarip insanlarda) sonuçlanacaktır. Bu nedenle, klasik istatistiksel protokolleri ( Fisher ) kullanamayız , bilgi toplama ucuz ve işlenmesi pahalı olduğunda optimaldir ve daha çok bilgiyi akarken kullanan Bayes yöntemlerini kullanan bir deney tasarımına yöneliriz .
Bu model bazen makine öğreniminde kullanılır; örneğin, bir reklam bağlantısına tıklamayı reddetmenin kullanılabilir bilgiler sağlaması dışında, önceden bilinenlere dayalı olarak sunmak için reklam seçimleri yapmak için kullanılır.
Gelen akıllı radyo , bu model genellikle spektrum için fırsatçı erişim için karar verme için kullanılmaktadır.