@Aram Ebtekar and I were discussing the definition of IB regret. It seems quite complicated, with three levels of mixture (!): prob mixture of Knightian uncertainty over prob mixtures. I understand the motivation for the inner two levels, but why now take a probabilistic mixture over crisp causal laws? It seems rather strange to weight laws in such as way that the choice of law is (epistemically?) stochastic, but then regret against the law itself is worst-case...
I do not have a precise objection to this, I’m just curious if there is some justification / intuition for why this is a reasonable definition?
First, Bayes-regret and worst-case-regret are standard concepts in classical RL theory, and the infra-versions are straightforward analogs.
Second, you don’t have to focus on the Bayes-regret necessarily. In fact, in ourpapers, we focus entirely on uniform (worst-case) regret bounds.
Third, instead of an ordinary prior over laws you can consider an infraprior over laws (i.e. have ambiguity in hypothesis-space and not just in outcome-space). The resulting notion of “infra-Bayes-regret” has both Bayes-regret and worst-case-regret as special cases.
Fourth, the justification is quite straightforward. If you have an (unambiguous i.e. ordinary probability distribution) prior over laws, and your performance metric is the Bayes-infra-expected utility, then the Bayes-regret is just the difference between the performance of your policy and the performance of an optimal policy that magically knows the true hypothesis. So it’s a very natural measure of your policy’s ability to learn the hypothesis.
That makes sense (particularly proving worst-case results).
Since a law, in general, means that the truth is outside of your hypothesis space and you can’t assign a probability distribution, in what sort of situation can you nevertheless justify a probability distribution over laws (rather than Knightian uncertainty)?
The truth is outside of my hypothesis class, but my hypothesis class probably contains a non-trivial law that is a coarsening of the truth, which is the whole point.
For example, you can imagine that you start with some kind of intractable simplicity prior. Then, for each hypothesis you choose a tractable law that coarsens it. You end up with a probability distribution over laws.
A different way to view this is, this is just a way to force your policy to have low-regret w.r.t. all/most hypothesis while weighing complex hypotheses less. For a complex hypothesis, you naturally expect learning it to be harder so you’re weighing its regret less. Typically, it’s only possible to have a uniform regret bound if you impose a bound on the complexity of hypotheses in some sense. Absent such a bound, your regret bound must be non-uniform. You can formalize it by explicitly allowing the per-hypothesis regret to depend on some complexity parameter, but the Bayes approach is an alternative. (Also, Bayes regret obviously implies per-hypothesis non-uniform regret with a 1/probability coefficient.)
Hmm, the thing I find strange about this is that it doesn’t do something ‘more complicated’. To me, I would think to take a credal set of crisp causal laws, and then try to minimize the maximum regret (so a minimum of a maximum of a minimum of a maximum).
That is, Bayesians take multilevel models that give them a probability distribution over probability distributions. They then can compare how well they will do (in expectation) to how well someone who knew the distribution would do.
InfraBayesians should then take multilevel models that give them a hypothesis over hypotheses, that is, a credal set of credal sets. They then can compare how well they will do (in expectation, which for them means in minimax of expectation) to how well someone (where the someone is an infrabayesian) who knew the hypothesis would do.
I was going to say something similar. After reading the first two posts of the sequence I really thought the role of credal sets in defining regret would be somewhat different.
In particular, consider to be the classical (non-infra) regret for a given policy on a given environment . For a given environment class, we previously considered two notions of learnability depending on the kind of uncertainty we had over . First, under knightian uncertainty, we required that our policy satisfy , and under Bayesian uncertainty, we required .[1] A credal set gives us a new way of quantifying our uncertainty over . Let be that credal set. Then we could instead require that . This has the property that if your happens to be the set of all distributions then the regret reduces to the usual regret, and if then you get Bayesian regret. Perhaps this is what @Vanessa Kosoy means by “infra-Bayes-regret” in her comment below. If so, I’m curious what results are known for this notion of regret.
What you propose here doesn’t address the issue of non-realizability at all. For example, let’s say is countable. Then any of the 3 regret criteria (uniform, Bayesian and your own “credal” proposal) implies that the algorithm would converge to a near-optimal policy for any given . This cannot work if some such is infeasible to optimize.
What does for mean? is a subset of , that is, a set of distributions over environments—so how can you take an environment ‘distributed’ according to unless you mean to do something with all the possible ways that prescribes that could be distributed.
@Aram Ebtekar and I were discussing the definition of IB regret. It seems quite complicated, with three levels of mixture (!): prob mixture of Knightian uncertainty over prob mixtures. I understand the motivation for the inner two levels, but why now take a probabilistic mixture over crisp causal laws? It seems rather strange to weight laws in such as way that the choice of law is (epistemically?) stochastic, but then regret against the law itself is worst-case...
I do not have a precise objection to this, I’m just curious if there is some justification / intuition for why this is a reasonable definition?
First, Bayes-regret and worst-case-regret are standard concepts in classical RL theory, and the infra-versions are straightforward analogs.
Second, you don’t have to focus on the Bayes-regret necessarily. In fact, in our papers, we focus entirely on uniform (worst-case) regret bounds.
Third, instead of an ordinary prior over laws you can consider an infraprior over laws (i.e. have ambiguity in hypothesis-space and not just in outcome-space). The resulting notion of “infra-Bayes-regret” has both Bayes-regret and worst-case-regret as special cases.
Fourth, the justification is quite straightforward. If you have an (unambiguous i.e. ordinary probability distribution) prior over laws, and your performance metric is the Bayes-infra-expected utility, then the Bayes-regret is just the difference between the performance of your policy and the performance of an optimal policy that magically knows the true hypothesis. So it’s a very natural measure of your policy’s ability to learn the hypothesis.
That makes sense (particularly proving worst-case results).
Since a law, in general, means that the truth is outside of your hypothesis space and you can’t assign a probability distribution, in what sort of situation can you nevertheless justify a probability distribution over laws (rather than Knightian uncertainty)?
The truth is outside of my hypothesis class, but my hypothesis class probably contains a non-trivial law that is a coarsening of the truth, which is the whole point.
For example, you can imagine that you start with some kind of intractable simplicity prior. Then, for each hypothesis you choose a tractable law that coarsens it. You end up with a probability distribution over laws.
A different way to view this is, this is just a way to force your policy to have low-regret w.r.t. all/most hypothesis while weighing complex hypotheses less. For a complex hypothesis, you naturally expect learning it to be harder so you’re weighing its regret less. Typically, it’s only possible to have a uniform regret bound if you impose a bound on the complexity of hypotheses in some sense. Absent such a bound, your regret bound must be non-uniform. You can formalize it by explicitly allowing the per-hypothesis regret to depend on some complexity parameter, but the Bayes approach is an alternative. (Also, Bayes regret obviously implies per-hypothesis non-uniform regret with a 1/probability coefficient.)
Hmm, the thing I find strange about this is that it doesn’t do something ‘more complicated’. To me, I would think to take a credal set of crisp causal laws, and then try to minimize the maximum regret (so a minimum of a maximum of a minimum of a maximum).
That is, Bayesians take multilevel models that give them a probability distribution over probability distributions. They then can compare how well they will do (in expectation) to how well someone who knew the distribution would do.
InfraBayesians should then take multilevel models that give them a hypothesis over hypotheses, that is, a credal set of credal sets. They then can compare how well they will do (in expectation, which for them means in minimax of expectation) to how well someone (where the someone is an infrabayesian) who knew the hypothesis would do.
(I see after reading further that Vanessa mentioned this possibility)
I was going to say something similar. After reading the first two posts of the sequence I really thought the role of credal sets in defining regret would be somewhat different.
In particular, consider
I’m ignoring
What you propose here doesn’t address the issue of non-realizability at all. For example, let’s say
Yes you are right. I got sidetracked thinking about credal sets and forgot the original goal. :)
What does