Alternative Function Approximation Parameterizations For Solving Games: An Analysis Of \(f\)-regression Counterfactual Regret Minimization

Abstract

Function approximation is a powerful approach for structuring large decision problems that has facilitated great achievements in the areas of reinforcement learning and game playing. Regression counterfactual regret minimization (RCFR) is a simple algorithm for approximately solving imperfect information games with normalized rectified linear unit (ReLU) parameterized policies. In contrast, the more conventional softmax parameterization is standard in the field of reinforcement learning and yields a regret bound with a better dependence on the number of actions. We derive approximation error-aware regret bounds for \((\Phi, f)\)-regret matching, which applies to a general class of link functions and regret objectives. These bounds recover a tighter bound for RCFR and provide a theoretical justification for RCFR implementations with alternative policy parameterizations (\(f\)-RCFR), including softmax. We provide exploitability bounds for \(f\)-RCFR with the polynomial and exponential li

Stats

• citations1
• S2 citations—
• github stars0
• HF likes0
• heat score2.26
• arxiv keydorazio2019alternative

Related papers

• Online Sub-sampling For Reinforcement Learning With General Function Approximation (2021)0.00
• Improved Regret For Efficient Online Reinforcement Learning With Linear Function Approximation (2023)0.00
• Prior-dependent Analysis Of Posterior Sampling Reinforcement Learning With Function Approximation (2024)0.00
• First-order Regret In Reinforcement Learning With Linear Function Approximation: A Robust Estimation Approach (2021)0.00
• Improved Regret Bound And Experience Replay In Regularized Policy Iteration (2021)0.00
• Minimax-optimal Off-policy Evaluation With Linear Function Approximation (2020)0.00
• Uniform-pac Bounds For Reinforcement Learning With Linear Function Approximation (2021)0.00
• Model-free Online Learning In Unknown Sequential Decision Making Problems And Games (2021)5.24