Pembalikan koin, proses pengambilan keputusan, dan nilai informasi

Bayangkan pengaturan berikut: Anda memiliki 2 koin, koin A yang dijamin adil, dan koin B yang mungkin atau mungkin tidak adil. Anda diminta untuk melakukan 100 koin terbalik, dan tujuan Anda adalah memaksimalkan jumlah kepala .

Informasi Anda sebelumnya tentang koin B adalah bahwa koin itu dibalik 3 kali dan menghasilkan 1 kepala. Jika aturan keputusan Anda hanya didasarkan pada membandingkan probabilitas yang diharapkan dari kepala 2 koin, Anda akan membalik koin A 100 kali dan selesai dengan itu. Ini benar bahkan ketika menggunakan estimasi Bayesian yang masuk akal (sarana posterior) dari probabilitas, karena Anda tidak memiliki alasan untuk percaya bahwa koin B menghasilkan lebih banyak kepala.

Namun, bagaimana jika koin B sebenarnya bias mendukung kepala? Tentunya "calon kepala" yang Anda berikan dengan membalik koin B beberapa kali (dan karena itu mendapatkan informasi tentang sifat statistiknya) akan bernilai dalam beberapa hal dan karenanya akan menjadi faktor dalam keputusan Anda. Bagaimana "nilai informasi" ini dijelaskan secara matematis?

Pertanyaan: Bagaimana Anda membuat aturan keputusan yang optimal secara matematis dalam skenario ini?

Bandit multi-bersenjata

Ini adalah kasus khusus dari masalah bandit Multi-Armed . Saya mengatakan kasus tertentu karena umumnya kita tidak tahu apa dari probabilitas kepala (dalam hal ini kita tahu salah satu koin memiliki probabilitas 0,5).

Masalah yang Anda ajukan dikenal sebagai dilema eksplorasi vs eksploitasi : apakah Anda menjelajahi opsi lain, atau apakah Anda tetap dengan yang menurut Anda adalah yang terbaik. Ada solusi optimal langsung dengan asumsi Anda tahu semua probabilitas : cukup pilih koin dengan probabilitas menang tertinggi. Masalahnya, seperti yang telah Anda singgung, adalah bahwa kami tidak yakin tentang probabilitas sebenarnya.

Ada banyak literatur tentang masalah ini, dan ada banyak algoritma deterministik, tetapi karena Anda menandai Bayesian ini, saya ingin memberi tahu Anda tentang solusi favorit pribadi saya: Bayesian Bandit !

Solusi Baysian Bandit

Pendekatan Bayesian untuk masalah ini sangat alami. Kami tertarik untuk menjawab, "Berapa probabilitas koin X lebih baik dari keduanya?".

Sebuah priori , dengan asumsi kita telah mengamati ada koin membalik belum, kita tidak tahu apa probabilitas koin B Heads mungkin, menunjukkan ini tidak diketahui . Jadi kita harus menetapkan distribusi seragam sebelumnya untuk probabilitas yang tidak diketahui ini. Atau, sebelumnya (dan posterior) kami untuk koin A secara sepele terkonsentrasi seluruhnya pada 1/2.$p_B$

Seperti yang telah Anda nyatakan, kami mengamati 2 ekor dan 1 kepala dari koin B, kami perlu memperbarui distribusi posterior kami. Dengan asumsi seragam sebelumnya, dan membalik adalah koin-membalik Bernoulli, posterior kami adalah . Membandingkan distribusi posterior atau A dan B sekarang:$Beta( 1 + 1, 1 + 2)$

Menemukan strategi yang kurang lebih optimal

Sekarang setelah kita memiliki eksterior, apa yang harus dilakukan Kami tertarik untuk menjawab "Berapa probabilitas koin B lebih baik dari keduanya" (Ingat dari perspektif Bayesian kami, meskipun ada jawaban pasti yang mana yang lebih baik, kami hanya dapat berbicara dalam probabilitas):

$w_B$$1 - w_B$$w_B$

1. Sample P_B from the posterior of coin B
2. If P_B > 0.5, choose coin B, else choose coin A.

Skema ini juga memperbarui sendiri. Ketika kami mengamati hasil memilih koin B, kami memperbarui posterior kami dengan informasi baru ini, dan memilih lagi. Dengan cara ini, jika koin B benar-benar buruk, kami akan memilihnya lebih sedikit, dan koin B sebenarnya sangat bagus, kami akan memilihnya lebih sering. Tentu saja, kita adalah orang Bayesian, maka kita tidak pernah bisa benar-benar yakin koin B lebih baik. Memilih secara probabilistik seperti ini adalah solusi paling alami untuk dilema eksplorasi-eksploitasi.

Ini adalah contoh khusus dari Thompson Sampling . Informasi lebih lanjut, dan aplikasi keren untuk iklan online, dapat ditemukan di makalah penelitian Google dan makalah penelitian Yahoo . Saya suka barang ini!

Ini adalah kasus sederhana dari masalah bandit multi-bersenjata . Seperti yang Anda perhatikan, Anda ingin menyeimbangkan informasi yang Anda kumpulkan dengan mencoba koin yang tidak dikenal saat Anda berpikir tidak optimal dalam jangka pendek melawan eksploitasi pengetahuan yang Anda miliki.

$1/2$

Secara umum, saya pikir Anda tidak dapat melepaskan diri dari masalah pemrograman dinamis, meskipun mungkin ada kasus khusus di mana strategi optimal dapat ditemukan dan diperiksa lebih sederhana.

Dengan seragam sebelumnya, di sinilah Anda harus berhenti:

$(0 ~ \text{heads}, 3 ~\text{tails}), (1 ~\text{head}, 5 ~\text{tails}), (2 ~\text{heads}, 6 ~\text{tails}), (3,7), (4,8),...(31,35), (32,35), (33,36), (34,37), ... (41,44), (42,44), ... (46,48), (47,48), (48,49), (49,50)$

$61.3299$

Saya menggunakan kode Mathematica berikut untuk menghitung ekuitas:

Clear[Equity];
Equity[n_, heads_, tails_] := Equity[n, heads, tails] = 
    If[n == 0, heads, 
       Max[1/2 + Equity[n - 1, heads, tails], 
           (heads + 1)/(heads + tails + 2) Equity[n - 1, heads + 1, tails] + 
           (tails + 1)/(heads + tails + 2) Equity[n - 1, heads, tails + 1]
           ]
      ]

Sebagai perbandingan, heuristik pengambilan sampel Thompson (yang diklaim Cam Davidson Pilon optimal) memberikan rata-rata 60.2907 kepala, lebih rendah sebesar 1.03915. Sampling Thompson memiliki masalah yang terkadang menjadi sampel B ketika Anda memiliki informasi yang cukup untuk mengetahui bahwa itu bukan taruhan yang baik, dan sering kali membuang-buang peluang untuk mengambil sampel B lebih awal, ketika informasi paling berharga. Dalam jenis masalah ini, Anda hampir tidak pernah acuh tak acuh di antara pilihan Anda, dan ada strategi optimal murni.

tp[heads_, tails_] := tp[heads, tails] = 
    Integrate[x^heads (1 - x)^tails / Beta[heads + 1, tails + 1], {x, 0, 1/2}]


Clear[Thompson];
Thompson[flipsLeft_, heads_, tails_] := Thompson[flipsLeft, heads, tails] = 
    If[flipsLeft == 0, heads, 
       Module[{p = tp[heads, tails]}, 
           p (1/2 + Thompson[flipsLeft-1,heads,tails]) + 
           (1-p)((heads+1)/(heads+tails+2)Thompson[flipsLeft-1,heads+1,tails] + 
           ((tails+1)/(heads+tails+2)) Thompson[flipsLeft-1,heads,tails+1])]]