  The Matroid Secretary Conjecture is a notorious open problem in online
optimization. It claims the existence of an $O(1)$-competitive algorithm for
the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid
appear one-by-one, revealing their weight at appearance, and the task is to
select elements online with the goal to get an independent set of largest
possible weight. $O(1)$-competitive MSP algorithms have so far only been
obtained for restricted matroid classes and for MSP variations, including
Random-Assignment MSP (RA-MSP), where an adversary fixes a number of weights
equal to the ground set size of the matroid, which then get assigned randomly
to the elements of the ground set. Unfortunately, these approaches heavily rely
on knowing the full matroid upfront. This is an arguably undesirable
requirement, and there are good reasons to believe that an approach towards
resolving the MSP Conjecture should not rely on it. Thus, both Soto [SIAM
Journal on Computing 2013] and Oveis Gharan & Vondrak [Algorithmica 2013]
raised as an open question whether RA-MSP admits an $O(1)$-competitive
algorithm even without knowing the matroid upfront.
  In this work, we answer this question affirmatively. Our result makes RA-MSP
the first well-known MSP variant with an $O(1)$-competitive algorithm that does
not need to know the underlying matroid upfront and without any restriction on
the underlying matroid. Our approach is based on first approximately learning
the rank-density curve of the matroid, which we then exploit algorithmically.
