CoChat
Sign Up
PreprintCited by 207Optimization and Variational AnalysisGame Theory and ApplicationsReinforcement Learning in Robotics

On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning

Open access
Gao, Bolin, Pavel, Lacra·2017·arXiv
DOI 10.48550/arxiv.1704.00805arXiv 1704.00805
Open this paper in CoChat — free accountOpen PDF

Abstract

In this paper, we utilize results from convex analysis and monotone operator theory to derive additional properties of the softmax function that have not yet been covered in the existing literature. In particular, we show that the softmax function is the monotone gradient map of the log-sum-exp function. By exploiting this connection, we show that the inverse temperature parameter determines the Lipschitz and co-coercivity properties of the softmax function. We then demonstrate the usefulness of these properties through an application in game-theoretic reinforcement learning.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1704.00805

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The Legendre transform of the lse is the negative entropy function, restricted to the probability simplex, and vice versa.

    “Lemma A28. The Legendre transform of the lse is the negative entropy function, restricted to the probability simplex and vice versa.”

    From Hopfield Networks is All You Need (2020) · cites this paper as Gao & Pavel (2017)

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 56

  1. [1][1] H. Young and S. Zamir, Handbook of Game Theory, Volume 4, 1st ed. Amsterdam: Elsevier, North-Holland, 2015. -
  2. [2][2] W. H. Sandholm, Population Games and Evolutionary Dynamics. Cambridge, MA, USA: MIT Press, 2010. -
  3. [3][3] J. Goeree, C. Holt and T. Palfrey, Quantal response equilibrium: A Stochastic Theory of Games. Princeton University Press, 2016. -
  4. [4][4] R. Sutton and A. Barto, Reinforcement Learning: An Introduction. Cambridge, MA, USA: MIT Press, 1998. -
  5. [5][5] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning. Cambridge, MA, USA: MIT Press, 2016. -
  6. [6][6] C. M. Bishop, Pattern Recognition and Machine Learning. Secaucus, NJ, USA: Springer, 2006. -
  7. [7][7] S. Boyd and L. Vandenberghe, Convex optimization, 1st ed. Cambridge, UK: Cambridge University Press, 2004. -
  8. [9][9] D. Bloembergen, K. Tuyls, D. Hennes, and M. Kaisers, 'Evolutionary dynamics of multi-agent learning: A survey', J. Artif. Intell. Res., vol. 53, no. 1, pp. 659-697, May 2015. -
  9. [10][10] G. Weiss, Multiagent Systems, 2nd ed. Cambridge, MA, USA: MIT Press, 2013. -
  10. [11][11] E. Alpaydin, Introduction to Machine Learning, 3rd ed. The MIT Press, 2014, p. 264. -
  11. [12][12] R. Luce, Individual Choice Behavior: A Theoretical Analysis. NY, Wiley, 1959. -
  12. [13][13] J. Bridle, 'Probabilistic Interpretation of Feedforward Classification Network Outputs, with Relationships to Statistical Pattern Recognition', Neurocomputing: Algorithms, Architectures and Applications, F. Soulie and J. Herault, eds., pp. 227-236, 1990. -
  13. [15][15] J. Smith and G. Price, 'The Logic of Animal Conflict', Nature, vol. 246, no. 5427, pp. 15-18, 1973. -
  14. [17][17] J. Weibull, ' Evolutionary Game Theory'. MIT Press, Cambridge, 1995. -
  15. [18][18] J. Hofbauer and W. H. Sandholm, 'Stable games and their dynamics', Journal of Economic Theory, vol. 144, no. 4, pp. 1665-1693, 2009. -
  16. [19][19] J. Hofbauer and E. Hopkins, 'Learning in perturbed asymmetric games', Games Economic Behav., vol. 52, pp. 133-152, 2005. -
  17. [20][20] A. Kianercy and A. Galstyan, 'Dynamics of Boltzmann Q-learning in two-player two-action games', Phys. Rev. E, vol. 85, no. 4, pp. 11451154, 2012. -
  18. [21][21] B. Gao and L. Pavel, 'On Passivity, Reinforcement Learning and HigherOrder Learning in Multi-Agent Finite Games', arXiv:1808.04464 [cs, math], Aug. 2018. - · arXiv
  19. [22][22] P. Coucheney, B. Gaujal and P. Mertikopoulos, 'Penalty-Regulated Dynamics and Robust Learning Procedures in Games', Mathematics of Operations Research, vol. 40, no. 3, pp. 611-633, 2015. -
  20. [23][23] P. Mertikopoulos and W. Sandholm, 'Learning in Games via Reinforcement and Regularization', Mathematics of Operations Research, vol. 41, no. 4, pp. 1297-1324, 2016. -
  21. [24][24] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis. Berlin: Springer-Verlag, 1998. -
  22. [25][25] H. Bauschke and P. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, 1st ed. New York: Springer, 2011. -
  23. [26][26] F. Facchinei and J.-S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems. Vol. I, Springer Series in Operations Research, Springer-Verlag, New York, 2003. -
  24. [27][27] J. Peypouquet. Convex optimization in normed spaces: theory, methods and examples. Springer, 2015. -
  25. [29][29] J. Baillon and G. Haddad, 'Quelques propri´ et´ es des op´ erateurs angleborn´ es etn-cycliquement monotones', Israel Journal of Mathematics, vol. 26, no. 2, pp. 137-150, 1977. -
  26. [30][30] N. Daw, J. O'Doherty, P. Dayan, B. Seymour and R. Dolan, 'Cortical substrates for exploratory decisions in humans', Nature, vol. 441, no. 7095, pp. 876-879, 2006. -
  27. [31][31] D. Lee, 'Neuroeconomics: Best to go with what you know?', Nature, vol. 441, no. 7095, pp. 822-823, 2006. -
  28. [32][32] J. D. Cohen, S. M. McClure, and A. J. Yu, 'Should I stay or should I go? How the human brain manages the trade-off between exploitation and exploration', Philosph. Trans. Roy. Soc. B: Bio. Sci., vol. 362, no. 1481, pp. 933-942, 2007. -
  29. [33][33] P. Bossaerts and C. Murawski, 'From behavioural economics to neuroeconomics to decision neuroscience: the ascent of biology in research on human decision making', Current Opinion in Behavioral Sciences, vol. 5, pp. 37-42, 2015. -
  30. [34][34] D. Koulouriotis and A. Xanthopoulos, 'Reinforcement learning and evolutionary algorithms for non-stationary multi-armed bandit problems', Applied Mathematics and Computation, vol. 196, no. 2, pp. 913-922, 2008. -
  31. [35][35] R. Zunino, P. Gastaldo, 'Analog implementation of the softmax function', In IEEE International Symposium on Circuits and Systems, vol 2, pp II-117, 2002. -
  32. [36][36] A. L. Yuille and D. Geiger, 'Winner-Take-All Mechanisms', In The Handbook of Brain Theory and Neural Networks, Ed. M. Arbib, MIT Press, 1995. -
  33. [37][37] I. M. Elfadel and J. L. Wyatt Jr., 'The softmax nonlinearity: Derivation using statistical mechanics and useful properties as a multiterminal analog circuit element', In Advances in Neural Information Processing Systems 6, J. Cowan, G. Tesauro, and C. L. Giles, Eds. San Mateo, CA: Morgan Kaufmann, 1994, pp. 882-887. -
  34. [38][38] I. M. Elfadel, 'Convex Potentials and their Conjugates in Analog MeanField Optimization', Neural Computation, vol. 7, no. 5, pp. 1079-1104, 1995. -
  35. [39][39] T. Genewein and D. A. Braun, 'Bio-inspired feedback-circuit implementation of discrete, free energy optimizing, winner-take-all computations', Biological, vol. 110, no. 2, pp. 135-150, Jun. 2016. -
  36. [40][40] T. Michalis, 'One-vs-each approximation to softmax for scalable estimation of probabilities', In Advances in Neural Information Processing Systems 29, pp. 4161-4169. 2016. -
  37. [41][41] P. Reverdy and N. Leonard, 'Parameter Estimation in Softmax DecisionMaking Models With Linear Objective Functions', IEEE Transactions on Automation Science and Engineering, vol. 13, no. 1, pp. 54-67, 2016. -
  38. [42][42] M. Kaisers, K. Tuyls, F. Thuijsman, S. Parsons, 'An evolutionary model of multi-agent learning with a varying exploration rate (Short Paper)', Proc. of 8th Int. Conf. on Autonomous Agents and Multiagent Systems (AA-MAS 2009), Decker, Sichman, Sierra and Castelfranchi (eds.), Budapest, Hungary, pp. 1255-1256., 2009. -
  39. [43][43] A. Martins and R. F. Astudillo. 'From softmax to sparsemax: A sparse model of attention and multi-label classification', arXiv:1602.02068 [cs.CL], Feb. 2016. - · arXiv
  40. [44][44] D. Leslie and E. Collins, 'Individual Q-Learning in Normal Form Games', SIAM Journal on Control and Optimization, vol. 44, no. 2, pp. 495-514, 2005. -
  41. [45][45] W. Sandholm, E. Dokumacı and R. Lahkar, 'The projection dynamic and the replicator dynamic', Games and Economic Behavior, vol. 64, no. 2, pp. 666-683, 2008. -
  42. [46][46] R. Laraki and P. Mertikopoulos, 'Higher order game dynamics', Journal of Economic Theory, vol. 148, no. 6, pp. 2666-2695, 2013. -
  43. [47][47] F. Alvarez, J. Bolte and O. Brahic, 'Hessian Riemannian Gradient Flows in Convex Programming', SIAM Journal on Control and Optimization, vol. 43, no. 2, pp. 477-501, 2004. -
  44. [48][48] A. Beck and M. Teboulle, 'Mirror descent and nonlinear projected subgradient methods for convex optimization', Operations Research Letters, vol. 31, no. 3, pp. 167-175, 2003. -
  45. [49][49] S. Shalev-Shwartz, 'Online Learning and Online Convex Optimization', Foundations and Trends in Machine Learning, vol. 4, no. 2, pp. 107-194, 2011. -
  46. [50][50] E. Hazan, 'Introduction to Online Convex Optimization', Foundations and Trends in Optimization, vol. 2, no. 3-4, pp. 157-325, 2016. -
  47. [51][51] A. Rangarajan, 'Self-annealing and self-annihilation: unifying deterministic annealing and relaxation labeling', Pattern Recognition, vol. 33, no. 4, pp. 635-649, 2000. -
  48. [52][52] C. Shen and H. Li, 'On the dual formulation of boosting algorithms', IEEE Trans. Pattern Anal. Mach. Intell. Feb. 25, 2010, 10.1109/TPAMI.2010.47. - · DOI
  49. [53][53] M. Harper, 'The replicator equation as an inference dynamic', arXiv:0911.1763 [math.DS], May. 2010. - · arXiv
  50. [54][54] Y. Sato and J. Crutchfield, 'Coupled Replicator Equations for the dynamics of learning in multiagent systems', Physical Review E, vol. 67, no. 1, 2003. -
  51. [56][56] E. Hopkins, 'Two Competing Models of How People Learn in Games', Econometrica, vol. 70, no. 6, pp. 2141-2166, 2002. -
  52. [57][57] R. Cominetti, E. Melo and S. Sorin, 'A payoff-based learning procedure and its application to traffic games', Games and Economic Behavior, vol. 70, no. 1, pp. 71-83, 2010. -
  53. [58][58] K. Tuyls, K. Verbeeck and T. Lenaerts, 'A selection-mutation model for Q-learning in multi-agent systems', in Proc. of the 2nd Int. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 693-700, 2003. -
  54. [59][59] M. Tokic and G. Palm, 'Value-difference based exploration: Adaptive control between ϵ -greedy and softmax', in KI 2011: Advances in Artificial Intelligence, vol. 7006. Heidelberg, Germany: Springer, 2011, pp. 335-346. -
  55. [60][60] P. Mertikopoulos, E. V. Belmega, and A. L. Moustakas, 'Matrix exponential learning: Distributed optimization in MIMO systems', in ISIT'12: Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012, pp. 3028-3032. -
  56. [61][61] K. Asadi and M. L. Littman, 'An Alternative Softmax Operator for Reinforcement Learning', arXiv:1612.05628 [cs, stat], Dec. 2016. · arXiv

Cited by

Sorted by citations

Authors
Gao, B., & Pavel, L.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2017
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1704.00805
arXiv
1704.00805
OpenAlex
W2606101940
Cited by
207
References
1
Citations by year
2025: 7 · 2024: 35 · 2023: 46 · 2022: 32 · 2021: 42 · 2020: 25 · 2019: 15 · 2018: 5
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
Keywords
softmax, inverse temperature, Lipschitz continuity, convex analysis, monotone operators

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review