Zinkevich's "online convex optimization" ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generalizes "regret minimization" learning algorithms from a linear settings to a convex setting and gives good "external regret". Is there a similar generalization for internal regret? (I'm not totally sure even what exactly that would mean.)
Try "No-regret learning in convex games" by Gordon, Greenwald and Marks http://portal.acm.org/citation.cfm?id=1390202 . Its abstract sounds like it probably answers your question, or at least anyone answering that question would cite or be cited by that paper.
This Avrim Blum paper points a connection between external and internal regret. According to its abstract, externa regret is a measure of how bad an algorithm is compared to the best fixed action, while internal regret compares to the best variation of that method (best fixed permutation of outputs, like reporting class A whenever the original algorithm reported class B).