Competitive regret

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In decision theory and machine learning, competitive regret refers to a performance measure that evaluates an algorithm's regret relative to an oracle or benchmark strategy. Unlike traditional regret, which compares against the best fixed decision in hindsight, competitive regret compares against decision-makers with different capabilities—either with greater computational resources or access to additional information.

The formal definition of competitive regret typically involves a ratio or difference between the regret of an algorithm and the regret of a reference oracle. An algorithm is considered to have "good" competitive regret if this ratio remains bounded even as the problem size increases. This framework has applications in various domains including online optimization, reinforcement learning, portfolio selection, and multi-armed bandit problems.

Competitive regret analysis provides researchers with a more nuanced evaluation metric than standard regret, helping them develop algorithms that can achieve near-optimal performance even under practical constraints and uncertainty.

In decision theory and machine learning, competitive regret refers to a performance measure that evaluates an algorithm's regret relative to an oracle or benchmark strategy. Unlike traditional regret, which compares against the best fixed decision in hindsight, competitive regret compares against decision-makers with different capabilities—either with greater computational resources or access to additional information.

The formal definition of competitive regret typically involves a ratio or difference between the regret of an algorithm and the regret of a reference oracle. An algorithm is considered to have "good" competitive regret if this ratio remains bounded even as the problem size increases. This framework has applications in various domains including online optimization, reinforcement learning, portfolio selection, and multi-armed bandit problems.

Competitive regret analysis provides researchers with a more nuanced evaluation metric than standard regret, helping them develop algorithms that can achieve near-optimal performance even under practical constraints and uncertainty.

Competitive regret to the oracle with full power

Consider estimating a discrete probability distribution p on a discrete set \mathcal{X} based on data X , the regret of an estimator q is defined as \max_{p\in \mathcal{P}} r_n (q,p). where \mathcal{P} is the set of all possible probability distribution, and r_n(q,p) = \mathbb{E} (D(p || q(X))). where D(p || q) is the Kullback–Leibler divergence between p and q .

Competitive regret to the oracle with limited power

Oracle with partial information

The oracle is restricted to have access to partial information of the true distribution p by knowing the location of p in the parameter space up to a partition. Given a partition \mathbb{P} of the parameter space, and suppose the oracle knows the subset P where the true p \in P . The oracle will have regret as r_n(P) = \min_q \max_{p\in P} r_n (q,p). The competitive regret to the oracle will be r_n^\mathbb{P}(q, \mathcal{P}) = \max_{P \in \mathbb{P}} (r_n(q,P) - r_n(P)).

The oracle knows exactly p , but can only choose the estimator among natural estimators. A natural estimator assigns equal probability to the symbols which appear the same number of time in the sample. The regret of the oracle is r_n^{nat} (p)= \min_{q\in \mathcal{Q}_{nat}} r_n(q,p), and the competitive regret is \max_{p \in \mathcal{P}} (r_n(q,p) - r_n^{nat} (p)).

Example

For the estimator q proposed in Acharya et al.(2013), r_n^{\mathbb{P}_\sigma} (q, \Delta_k) \leq r^{nat}_n(q, \Delta_k) \leq \tilde{\mathcal{O}} (\min (\frac{1}{\sqrt{n}}, \frac{k}{n})). Here \Delta_k denotes the k-dimensional unit simplex surface. The partition \mathbb{P}_\sigma denotes the permutation class on \Delta_k , where p and p' are partitioned into the same subset if and only if p' is a permutation of p .

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1343145724 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.