AIXI-with-optimal-predictors: I believe this is relatively straightforward. However, my plan for the next step was adapting these results to a decision rule based on logical counterfactuals in a way which produces metathreat equilibria.
Bounded Nash equilibria: I don’t think the concept is entirely novel. I’ve seen some papers which discuss Nash-like equilibria with computational resource bounds, although the the area seems to remain largely unexplored. The particular setting I use here is not very relevant to what you’re suggesting since finding Nash equilibria is non-polynomial in the number of strategies whereas here I keep the number of strategies constant. Instead, the complexity comes from the dependence of the payoff tensor on the parameter sampled from μk.
Your description of Theorem 1 is more or less correct except there’s only a “payoff vector” here since this is a 1 player setting. The multiplayer setting is used in Corollary 2.
Regarding dependence on game size, it is not as bad as exponential. The Lipton-Markakis-Mehta algorithm finds ϵ-equilibria in time O(nlognϵ2)
AIXI-with-optimal-predictors: I believe this is relatively straightforward. However, my plan for the next step was adapting these results to a decision rule based on logical counterfactuals in a way which produces metathreat equilibria.
Bounded Nash equilibria: I don’t think the concept is entirely novel. I’ve seen some papers which discuss Nash-like equilibria with computational resource bounds, although the the area seems to remain largely unexplored. The particular setting I use here is not very relevant to what you’re suggesting since finding Nash equilibria is non-polynomial in the number of strategies whereas here I keep the number of strategies constant. Instead, the complexity comes from the dependence of the payoff tensor on the parameter sampled from μk.
Your description of Theorem 1 is more or less correct except there’s only a “payoff vector” here since this is a 1 player setting. The multiplayer setting is used in Corollary 2.
Regarding dependence on game size, it is not as bad as exponential. The Lipton-Markakis-Mehta algorithm finds ϵ-equilibria in time O(nlognϵ2)