Arxiv hàng ngày

Đây là trang tổng hợp các bài báo về trí tuệ nhân tạo được xuất bản trên toàn thế giới.
Trang này sử dụng Google Gemini để tóm tắt nội dung và hoạt động phi lợi nhuận.
Bản quyền của các bài báo thuộc về tác giả và tổ chức liên quan; khi chia sẻ, chỉ cần ghi rõ nguồn.

MF-OML: Học tăng cường trường trung bình trực tuyến với các biện pháp nghề nghiệp cho các trò chơi dân số lớn

Created by
  • Haebom

Tác giả

An Nhiên Hồ, Junzi Zhang

Phác thảo

Bài báo này đề xuất Học Đo lường Nghề nghiệp Trường Trung bình (MF-OML), một thuật toán học tăng cường trường trung bình trực tuyến để tính toán cân bằng Nash gần đúng của các trò chơi đối xứng tuần tự tập thể quy mô lớn. MF-OML là thuật toán học tăng cường đa tác nhân hoàn toàn thời gian đa thức đầu tiên có thể giải quyết được các cân bằng Nash một cách có thể chứng minh được (với sai số xấp xỉ trường trung bình bằng không khi số lượng người chơi N tiến tới vô cực) vượt ra ngoài các trò chơi tổng bằng không và các biến thể trò chơi tiềm ẩn. Đối với các trò chơi có tính đơn điệu Lasry-Lions mạnh, thuật toán này đạt được giới hạn trên hối tiếc có xác suất cao là $\tilde{O}(M^{3/4}+N^{-1/2}M)$, được đo bằng độ lệch tích lũy so với cân bằng Nash, và đối với các trò chơi chỉ có tính đơn điệu Lasry-Lions, thuật toán này đạt được giới hạn trên hối tiếc là $\tilde{O}(M^{11/12}+N^{- 1/6}M)$, trong đó M là tổng số tập và N là số tác nhân trong trò chơi. Như một sản phẩm phụ, chúng tôi thu được thuật toán tính toán hội tụ toàn cục dễ xử lý đầu tiên để tính toán cân bằng Nash gần đúng của các trò chơi trường trung bình đơn điệu.

Takeaways, Limitations

Takeaways:
Chúng tôi đề xuất một thuật toán mới, MF-OML, để tính toán hiệu quả các cân bằng Nash gần đúng cho các trò chơi đối xứng tuần tự tập thể quy mô lớn.
Thuật toán có độ phức tạp thời gian đa thức hoàn toàn đầu tiên có thể giải quyết được trạng thái cân bằng Nash ngoài các trò chơi tổng bằng không và các biến thể của trò chơi tiềm năng.
Chúng tôi trình bày một thuật toán tính toán hội tụ toàn cục dễ sử dụng để tính toán cân bằng Nash gần đúng của trò chơi trường trung bình đơn điệu.
Lasry-Lions đưa ra giới hạn trên rõ ràng về sự hối tiếc trong điều kiện đơn điệu.
Limitations:
Hiệu suất của thuật toán phụ thuộc vào điều kiện đơn điệu Lasry-Lions và có thể không áp dụng được cho tất cả các trò chơi.
Giới hạn trên của sự hối tiếc bao gồm lỗi xấp xỉ trường trung bình và có thể không phản ánh hoàn hảo sự khác biệt so với cân bằng Nash thực tế.
Hiệu suất thực tế của thuật toán có thể thay đổi tùy thuộc vào đặc điểm của trò chơi và cần phải xác minh thử nghiệm thêm.
👍