Chiến lược Kelly không thể thất bại

 (win-vector.com)
3 điểm bởi GN⁺ 2024-12-20 | 1 bình luận | Chia sẻ qua WhatsApp
  • Trong Next Card Bet, nơi liên tục theo dõi phân bố màu của bộ bài 52 lá, chiến lược Kelly — khác với tính chất phương sai cao thường thấy — luôn biến vốn ban đầu $1 thành khoảng $9.08 khi kết thúc
  • Quy tắc đặt cược rất đơn giản: nếu số lá đỏ còn lại r bằng số lá đen b thì nghỉ; nếu một màu còn lại nhiều hơn, đặt cược |r - b| / (r + b) số vốn hiện có vào màu đó
  • Ngay cả khi chạy 10.000 bộ bài được xáo bằng Python, vốn cuối cùng vẫn nằm trong khoảng 9.081329549427776~9.081329549427803, tạo ra lợi nhuận lớn hơn chiến lược nhân đôi chỉ cược ở lá cuối cùng mà không có biến động
  • Chứng minh được xây dựng như một danh mục: chia đều vốn ban đầu cho (52 choose 26) = 495,918,532,948,104 cách sắp xếp đỏ/đen có thể có, và chỉ một chiến lược con khớp với bộ bài thực tế được nhân đôi liên tiếp 52 lần
  • Mức thay đổi tổng vốn của danh mục này giống với mẫu lợi nhuận của chiến lược Kelly, khiến chiến lược Kelly vốn thường có thể thua tiền trở thành chiến lược có phương sai 0 trong trò chơi này

Quy tắc và trực giác của Next Card Bet

  • Chiến lược phân bổ cược Kelly là cách xác định tỷ lệ đặt cược bằng cách tận dụng thông tin hoặc độ lệch trong bối cảnh cờ bạc
  • Chiến lược Kelly thông thường được biết đến là chiến lược tấn công có phương sai cao, và nếu đặt cược lớn hơn tỷ lệ Kelly thì rủi ro phá sản có thể tăng lên
  • Trong “Next Card Bet” trong Mathematical Puzzles của Peter Winkler, chiến lược này hoạt động với phương sai 0 và không có rủi ro
  • Trò chơi bắt đầu với bộ bài tiêu chuẩn 52 lá
    • Có 26 lá đỏ và 26 lá đen
    • Sau khi xáo bài, lật từng lá một; lá đã lật không được đưa lại vào bộ bài
    • Người chơi có thể đặt cược một tỷ lệ tùy ý của số vốn hiện có vào việc lá tiếp theo là đỏ hay đen
    • Tỷ lệ trả thưởng là 1:1, và vốn ban đầu là $1
  • Nếu đếm các lá đã xuất hiện, có thể biết số lượng từng màu còn lại trong phần bộ bài chưa nhìn thấy
    • Nếu không đặt cược cho đến lá cuối cùng, có thể biết chắc màu của lá còn lại
    • Chiến lược đơn giản này đặt toàn bộ vốn vào lá cuối cùng và có thể an toàn làm vốn tăng gấp 2 lần

Tỷ lệ đặt cược Kelly

  • Chiến lược Kelly chọn mức cược tối đa hóa kỳ vọng của log vốn cuối cùng
  • Gọi số lá đỏ còn lại là r, số lá đen còn lại là b; nếu r > b, xác suất lá đỏ xuất hiện là r / (r + b)
  • Kỳ vọng log vốn được tối đa hóa theo biểu thức sau
    • P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction)
  • Tại điểm đạo hàm của biểu thức này bằng 0, tỷ lệ đặt cược là (r - b) / (r + b)
  • Toàn bộ chiến lược chỉ chấp nhận rủi ro tương ứng với chênh lệch giữa hai màu còn lại
    • Nếu r = b thì không cược
    • Nếu r > b thì cược tỷ lệ |r - b| / (r + b) của vốn hiện có vào “red”
    • Nếu b > r thì cược tỷ lệ |r - b| / (r + b) của vốn hiện có vào “black”

Kết quả mô phỏng Python

  • Ví dụ Python chạy chiến lược Kelly bằng hàm run_bets(is_red)
    • Bắt đầu với stake là 1.0
    • Cập nhật số lá đỏ và lá đen còn lại sau mỗi lá
    • Cược vào màu còn lại nhiều hơn với tỷ lệ abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining)
    • Nếu đoán đúng, số tiền cược đó được trả về gấp 2 lần; nếu sai thì mất
  • Bộ sinh số ngẫu nhiên dùng np.random.default_rng(2024)
  • Khi tạo 10.000 bộ bài có 26 lá đỏ trong tổng 52 lá, kết quả gần như hội tụ về cùng một giá trị
    • Giá trị nhỏ nhất: 9.081329549427776
    • Giá trị lớn nhất: 9.081329549427803
  • Chênh lệch kết quả nhỏ hơn 1e-8, và trong mọi lần chạy đều tạo ra lợi nhuận khoảng 9.08 lần vốn ban đầu
  • Lợi nhuận 9.08 lần lớn hơn nhiều so với chiến lược chỉ cược vào lá cuối cùng để an toàn nhận mức gấp 2 lần

Chứng minh bằng danh mục tạo phương sai 0

  • Số cách sắp xếp lá đỏ và lá đen có thể có là (52 choose 26) = 495,918,532,948,104
  • Sử dụng kết quả tiêu chuẩn rằng trong một bộ bài được xáo đúng cách, tất cả các chuỗi đỏ/đen này xuất hiện với xác suất như nhau
  • Chiến lược danh mục coi mỗi chuỗi đỏ/đen có thể có là một chiến lược con
    • Phân bổ 1 / (52 choose 26) vốn ban đầu cho mỗi chiến lược con ứng với một chuỗi
    • Các chiến lược con chỉ quản lý tiền của riêng mình và không phân bổ lại cho nhau
    • Mỗi chiến lược con giả định chuỗi được gán cho nó chính là bộ bài thực tế, và ở mỗi lá sẽ cược toàn bộ vào màu tương ứng
  • Tất cả các chiến lược con khác với bộ bài thực tế cuối cùng sẽ cược toàn bộ vào một lá sai và phá sản
  • Chỉ một chiến lược con khớp chính xác với bộ bài thực tế mới đoán đúng cả 52 lá và trở thành 2^52 lần
  • Vì vậy, lợi nhuận cuối cùng của toàn bộ danh mục luôn là cùng một giá trị, bất kể thứ tự bài
    • $1 / (52 choose 26) * 2^52
    • khoảng $9.08

Sự tương đồng giữa danh mục và chiến lược Kelly

  • Trong danh mục, các chiến lược con chưa phá sản dự đoán lá tiếp theo là đỏ hoặc đen
  • Khi còn r lá đỏ và b lá đen, tỷ lệ dự đoán của các chiến lược con tuân theo tỷ lệ các màu còn lại
  • Khi lá tiếp theo được lật, nhóm dự đoán sai phá sản, còn nhóm dự đoán đúng được nhân đôi vốn
  • Lúc này, mức thay đổi tổng vốn của danh mục khớp chính xác với mẫu lợi nhuận của chiến lược Kelly, vốn cược |r - b| / (r + b) vào màu còn lại nhiều hơn
  • Lý do chiến lược Kelly có phương sai 0 là vì nó vận động giống hệt một chiến lược danh mục vốn tự thân có phương sai 0

Khác biệt so với chiến lược Kelly thông thường

  • Chiến lược Kelly thường tối đa hóa tốc độ tăng trưởng kỳ vọng của log vốn trong khi tránh phá sản
  • Nhưng ngoài điều đó, chiến lược Kelly thông thường không đảm bảo nhiều; trên thực tế vẫn có thể thua tiền và thường có phương sai cao
  • Trong trò chơi bài này, ngay cả khi phát sinh thua lỗ, phân bố màu của bộ bài sẽ trở nên mất cân bằng hơn, khiến điều kiện về sau thuận lợi hơn
  • Nếu đặt cược đủ nhỏ, lợi thế lớn hơn về sau sẽ bù lại phần vốn đã mất ở các lần cược sai
  • Cấu trúc này gợi nhớ đến các giai đoạn khám phá và khai thác trong những bài toán như A/B testing

Tài liệu tham khảo

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-12-20
Các ý kiến trên Hacker News

  • Để chiến lược này luôn đúng, tiền cược phải có thể chia nhỏ vô hạn
    Ví dụ, nếu 26 lá bài đỏ dồn ở phía trên bộ bài, khoản cược ban đầu $1.00 sẽ giảm xuống 0.000000134 rồi lại tăng lên 9.08

    • Nếu tiền cược ban đầu là $1e12 thì ngay cả trong trường hợp xấu nhất cũng có thể tránh được lỗi làm tròn nghiêm trọng. Có lẽ trong đó có một bài học cuộc đời
    • Nhận xét hay. Khi thử nghiệm, hệ thống này cực kỳ nhạy với việc lượng tử hóa hoặc làm tròn số tiền đặt cược
      Giá trị kỳ vọng nằm xấp xỉ đúng chỗ, nhưng phương sai tăng rất nhanh. Vì vậy ngoài trường hợp quan trọng này, nhìn chung nó cũng khá bất ổn
    • Tôi đã thêm ghi chú tiếp theo về trường hợp tiền cược rời rạc ở đây: https://win-vector.com/2024/12/21/kelly-betting-with-discret...
      Có một chiến lược quy hoạch động đã biết bảo đảm lợi nhuận $8.08 từ khoản cược $1. Cách chỉ làm tròn đơn giản chiến lược Kelly sẽ không cho ra kết quả này
    • Hầu hết đều đi đến điểm này. Phải xem việc tung đồng xu như toàn bộ các lần tung trong một khoảng thời gian rất dài, và để chiến lược hoạt động nguyên vẹn thì không được bỏ qua dù chỉ một lần
      Chỉ cần lỡ một lần là có thể bỏ lỡ một đoạn liên tiếp có lãi hoặc một lần cụ thể tạo ra lợi nhuận lớn. Nếu vẽ biểu đồ giá theo thời gian giống như biểu đồ Renko, nó trông cũng tương tự bất kỳ biểu đồ hàng hóa nào
      Trong giao dịch cổ phiếu/tiền mã hóa/ngoại hối ngoài đời, điều đó có nghĩa là phải thực hiện gần như mọi giao dịch; nếu không, hiệu năng chiến lược sẽ giảm. Cũng như trong thí nghiệm không được đổi đồng xu, trong giao dịch cũng không được đổi mã, bỏ lỡ giao dịch, và phải duy trì trong thời gian rất dài
      Không cần phải nói, điều này đòi hỏi tính nhất quán khủng khiếp, và khi tiền thật tham gia thì áp lực cũng lớn hơn. Lặp lại mỗi ngày sẽ rất hao mòn tinh thần và thể chất, khó mà duy trì lâu dài
    • Cặp đối lập với điều đó cũng giống như nói rằng nếu có tiền vô hạn thì Martingale không thể thất bại

  • Một nhánh thú vị liên quan đến Kelly là nghịch lý Proebsting
    Trong xác suất học, nghịch lý Proebsting là một lập luận dường như cho thấy tiêu chuẩn Kelly có thể dẫn đến phá sản. Về mặt toán học có thể giải quyết được, nhưng nó đặt ra những vấn đề thú vị khi áp dụng Kelly trong thực tế, đặc biệt là trong đầu tư. Edward O. Thorp lần đầu thảo luận về nó vào năm 2008, và nó được đặt theo tên người đề xuất Todd Proebsting
    https://en.wikipedia.org/wiki/Proebsting%27s_paradox

    • Trích ngay từ trang đó, cách dễ dàng để bác bỏ nghịch lý này là thấy rằng Kelly giả định xác suất không thay đổi
      Tức là Kelly phù hợp khi bạn biết xác suất, và xác suất đó không đổi
      Nếu không biết xác suất hoặc xác suất có thể thay đổi, cách tiếp cận đúng có lẽ phải phức tạp hơn Kelly

  • Nội dung rất đẹp, nhưng lập luận danh mục đầu tư có vẻ là một đường vòng không cần thiết. Có thể chứng minh bằng quy nạp trong hai dòng

    1. Trường hợp cơ sở, mức trả thưởng của (0,1) hoặc (1,0) là 2
    2. Ở trạng thái (r,b), r >= b, nếu có $X và đặt (r-b)/(r+b) vào đỏ, thì khi rút đỏ và thắng, mức trả thưởng là X * (1+(r-b)/(r+b)) * 2^(r+b-1) / (r+b-1 choose r-1) = X * 2^(r+b) * r / ((r+b) * (r+b-1 choose r-1)) = X * 2^(r+b) / (r+b choose r)
      Tương tự, khi rút đen và thua, mức trả thưởng là X * (1-(r-b)/(r+b)) * 2^(r+b-1) / (r+b-1 choose r) = X * 2^(r+b) * b / ((r+b) * (r+b-1 choose r)) = X * 2^(r+b) / (r+b choose r). QED
    • Vì sao chứng minh quy nạp đó lại không phải là đường vòng không cần thiết?

  • Như trong câu hỏi #14 của sách phỏng vấn tài chính định lượng của Timothy Falcon, có một trò chơi bài rất giống: lật các lá trong bộ bài và quyết định khi nào dừng. Đỏ được tính là $1, đen là −$1
    Gwern đã giải thích trò này và còn viết mã để kiểm chứng chiến lược dừng tối ưu: https://gwern.net/problem-14

    • Nếu theo thông lệ tài chính tiêu chuẩn thì đen phải là +$1, đỏ là -$1. Tức là phải khớp với quy ước “lãi đen” và “lỗ đỏ”

  • Khi còn là thiếu niên, tôi phát hiện ra rằng nếu đếm bài và đoán màu còn lại nhiều hơn trong bộ bài thì lúc nào cũng có thể đoán đúng hơn một nửa
    https://en.wikipedia.org/wiki/TRS-80_Model_100
    Tôi đã viết mô phỏng trên đó và chưa từng thất bại lần nào. Gần đây nhớ lại, tôi chạy bằng script Python 30 triệu lần và vẫn không thất bại
    Nghĩ xem có thể dùng việc này vào đâu, tôi nghĩ đến (i) cá cược, (ii) ảo thuật, nhưng cả hai đều không mấy hứa hẹn
    Với cá cược, có thể đặt $1000 ăn $10 của đối phương, nhưng đó không phải con đường kiếm lợi nhuận lớn, và nếu nhầm hoặc bị lừa thì có thể mất rất nhiều tiền. Nghĩ lại thì có lẽ tái cấu trúc thành dạng cược gộp liên tiếp (parlay) sẽ tốt hơn
    Với ảo thuật thì quá chậm. Tôi đã nghĩ ra lời dẫn kiểu “Các nhà cận tâm lý học không thể chứng minh năng lực tiên tri một cách ổn định bằng những lá Zener đẹp mắt, nhưng tôi đã tạo ra một giao thức có thể chứng minh được mọi lần!”, nhưng thấy chưa đủ thú vị. Lật hết một bộ bài mất thời gian, cũng không trông như phép màu, và để bác bỏ giả thuyết không ở p=0.01 thì phải làm liên tiếp 7 lần. Có lẽ người có khả năng làm chủ sân khấu tốt hơn thì làm được, nhưng tôi đã bỏ cuộc

    • Điều này làm tôi nhớ đến một thuật toán tôi thích. Trong một danh sách có bao nhiêu mục khác nhau đi nữa, nếu tồn tại phần tử chiếm đa số, thì có thể tìm nó trong thời gian O(N) và không gian O(1)
      Thỉnh thoảng tôi đưa bài toán suy ra thuật toán này như một câu đố, nhưng chưa ai giải được. Tôi cũng không giải được
      https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
    • Số thứ tự bài có thể có đủ lớn đến mức có thể phải lo vấn đề nguồn giả ngẫu nhiên không quét được đúng toàn bộ không gian. Trong trường hợp đó, mô phỏng có thể rất dễ gây hiểu lầm
      Ngay cả khi có đủ entropy thì 30 triệu lần chắc chắn vẫn chưa đủ

  • Tiêu chuẩn Kelly là một trong những khái niệm lý thuyết trò chơi tôi thích, và đặc biệt được dùng nhiều trong quản lý vốn của các con bạc chuyên nghiệp như người chơi poker
    Đây là một cách hay để giúp hiểu nên quản lý tài chính và mức cược thế nào để tránh rủi ro quá lớn hoặc phá sản trong khi vẫn tiến đều về phía trước, nhưng nó thường bị áp dụng sai trong lĩnh vực đó. Kelly xử lý kết quả nhị phân; nếu áp dụng vào tình huống kết quả không nhị phân, tùy cách nhìn vào toán học mà kết quả có thể trông gần đúng nhưng lại lệch đi một chút

    • Tiêu chuẩn Kelly có vẻ tuyệt vời cho nhiều dạng cờ bạc, nhưng poker có thể là ngoại lệ
      Poker là chơi với những người chơi khác, nên tiện ích của một phân bố chip nhất định có vẻ phải phức tạp hơn chỉ đơn giản là số chip đang có
      Tôi không phải người chơi poker
    • Câu “Kelly xử lý kết quả nhị phân” là sai. https://entropicthoughts.com/the-misunderstood-kelly-criteri...
      Tiêu chuẩn Kelly khái quát hóa tốt cho cả các phân bổ liên tục, đồng thời và phức tạp
      Thứ cần có chỉ là danh sách các hành động có thể chọn, và phân phối xác suất kết hợp của kết quả tài sản sau mỗi hành động. Hành động cũng có thể là hành động phức hợp với kết quả liên tục
    • Nói tiêu chuẩn Kelly xử lý kết quả nhị phân là đúng, và vì vậy nó không phù hợp với poker
      Trong poker, thắng thua không phải nhị phân mà số tiền thắng hoặc thua khác nhau, nên dùng giá trị kỳ vọng. Sau khi tính giá trị kỳ vọng xấp xỉ, người ta còn dùng thêm máy tính phương sai, chẳng hạn https://www.primedope.com/poker-variance-calculator/, để xem về dài hạn, trong một số ván bài nhất định, có khả năng thắng bao nhiêu và thường xuyên đến mức nào
    • Liệu cách này có hiệu quả khi cược màu trong roulette không?
      Có vẻ sẽ tốn rất nhiều thời gian mà không thắng cũng chẳng thua

  • Nếu rút xuống những con số dễ xử lý hơn, chẳng hạn bộ bài gồm 2 lá đen và 2 lá đỏ, thì sẽ là một bản demo tốt hơn
    Lượt 1 thì r = b nên không cược
    Lượt 2 cược 1/3 vào màu không xuất hiện ở lượt 1
    Lượt 3, nếu đã sai ở lượt 2 thì chỉ còn 2/3 tiền cược, nhưng vì biết màu của hai lá tiếp theo nên mỗi lần sẽ nhân đôi, sau lượt 3 trở thành 4/3 số tiền cược ban đầu. Nếu đã đúng thì tiền cược là 4/3, nhưng còn lại một lá đỏ và một lá đen nên lượt này không cược
    Lượt 4 thì biết màu của lá cuối cùng, nên nhân đôi tiền thành 8/3 số tiền cược ban đầu
    Và bài tập dành cho độc giả là chứng minh tính tối ưu; tuy khá straightforward, nhưng tôi không tin là có một chứng minh ngắn

    • Đúng. Tuy nhiên với bộ 4 lá, ở lượt 3 chỉ có một nhánh không tầm thường
      Vì vậy nếu bắt đầu bằng ví dụ 4 lá rồi cho xem sơ đồ cây của trường hợp 5 lá và 6 lá, các con số vẫn dễ xử lý và sẽ hữu ích để xây dựng trực giác quy nạp lên trường hợp tổng quát
    • Tôi theo được lập luận tổng quát, nhưng chưa đến mức bị thuyết phục vì sao kết quả lại đúng bằng nhau bất kể thứ tự các lá bài

  • Trên thực tế có nhiều yếu tố khiến việc dùng Kelly khó hơn so với ví dụ đồ chơi
    Quy mô vốn là gì? Tiền mặt đang có? Tổng tài sản ròng? Tài sản ròng thanh khoản? Thu nhập lao động trong tương lai?
    Tùy quy mô vốn mà nhiều yếu tố sẽ xuất hiện. Ví dụ, nếu vốn là $100 và mất hết thì thường không phải chuyện lớn. Nhưng nếu vốn là $1 million thì sẽ ngần ngại hơn nhiều khi đặt nó vào rủi ro
    Giá trị kỳ vọng là gì? Có biết được không? Có ổn định không? Trò chơi có trung thực không?
    Tùy các đặc tính thống kê của giá trị kỳ vọng, cách tiếp cận quy mô cược phải được điều chỉnh đáng kể. Trong các lĩnh vực chỉ có thể ước tính giá trị kỳ vọng và có nhiều kẻ gian, chẳng hạn poker, phải quyết định kích thước cược dưới mức bất định lớn
    Có thể dùng mức cược nào?
    Trên thực tế không có một dải mức cược liên tục. Thường chỉ có các mức rời rạc như từ $5 đến $500 theo đơn vị $5 hoặc $25. Nếu vốn xuống quá thấp thì bị đẩy ra khỏi cuộc chơi, còn nếu quá cao thì không thể tối đa hóa lợi nhuận nữa
    Cuối cùng, vì những phức tạp này mà các con bạc chuyên nghiệp thường cược theo half Kelly hoặc quarter Kelly

    • Trên thực tế, không chỉ không thể tạo ra mức cược liên tục, mà còn có thể phải trả chi phí cho chính quyền được đặt cược
      Trong giao dịch có spread và phí hoa hồng, còn ở bàn casino có rake

  • Việc kết quả không có phương sai rất hay. Nhưng cũng chính vì thế, do cấu trúc đặc thù của bài toán này, cảm giác như phải có một chiến lược nào đó cho lợi nhuận kỳ vọng cao hơn
    Ở đây có biết chiến lược Kelly có tối ưu không?

    • Cảm giác như nó sẽ có giá trị kỳ vọng cao nhất. Tôi đã thử chiến lược lật hết bài cho đến khi chỉ còn một màu, rồi mỗi lần cược toàn bộ; chạy một triệu lần thì ra 9,08
      Ban đầu tôi nghĩ các chiến lược này rất khác nhau, nhưng thực ra không hẳn vậy. Chiến lược Kelly cũng làm tương tự khi chỉ còn một màu. Khác biệt là chiến lược này không làm gì trước thời điểm đó
      Dù vậy, cả hai vẫn có vẻ như những trường hợp cực hạn. Khi chỉ còn một màu, cược toàn bộ vào màu đó là nước đi đúng duy nhất, và rốt cuộc vấn đề là làm gì trước đó. Không làm gì và Kelly là những chiến lược duy nhất trông có vẻ tốt
    • “Tối ưu” nghĩa là gì? Có phải là sẵn sàng chấp nhận rủi ro phá sản để có giá trị kỳ vọng cao hơn không?
    • Trong sách, họ nói là tối ưu đối với tập hợp các chiến lược được gọi là “hợp lý”
      Tuy nhiên lập luận đó không diễn ra tự nhiên như chứng minh cho thấy phương sai bằng 0, nên tôi đã không đưa vào. Bản gốc dường như cũng gọi các chiến lược con trong danh mục là “chiến lược thuần túy” và gợi ý một chứng minh theo lý thuyết trò chơi
    • Trong trò chơi này, miễn là tuân theo quy tắc rằng nếu bộ bài còn lại đều cùng một màu thì phải cược toàn bộ số tiền mình có vào màu đó, giá trị kỳ vọng của mọi chiến lược đều như nhau
    • Tiêu chí Kelly chính là chiến lược tạo ra lợi nhuận tốt hơn nhờ cấu trúc độc đáo của bài toán này

  • Có vẻ bài toán này và lời giải bắt nguồn từ Thomas Cover
    Tôi không nhớ ví dụ cụ thể này, nhưng tôi đã học tiêu chí Kelly trong một lớp do Thomas Cover dạy. Ông là một trong những giảng viên tôi yêu thích nhất, và bất kỳ cuộc thảo luận nào với ông cũng đều thú vị và đáng giá. Xin yên nghỉ

    • Ông cũng để lại nhiều bài báo thú vị trong lĩnh vực này, và một số trong đó chiếm một phần đáng kể trong cuốn sách về tiêu chí Kelly