Aristotle describes the regress problem in his logical work Posterior Analytics I.2:
b5. Some hold that, owing to the necessity of knowing the primary premisses, there is no scientific knowledge. Others think there is, but that all truths are demonstrable. Neither doctrine is either true or a necessary deduction from the premisses.
b8. The first school [agnostics?], assuming that there is no way of knowing other than by demonstration, maintain that an infinite regress is involved, on the ground that if behind the prior stands no primary, we could not know the posterior through the prior (wherein they are right, for one cannot traverse an infinite series): if on the other hand — they say — the series terminates and there are primary premisses, yet these are unknowable because incapable of demonstration, which according to them is the only form of knowledge. And since thus one cannot know the primary premisses, knowledge of the conclusions which follow from them is not pure scientific knowledge nor properly knowing at all, but rests on the mere supposition that the premisses are true.
b15. The other party [sophists?] agree with them as regards knowing, holding that it is only possible by demonstration, but they see no difficulty in holding that all truths are demonstrated, on the ground that demonstration may be circular and reciprocal.
b18. Our own doctrine is that not all knowledge is demonstrative: on the contrary, knowledge of the immediate premisses is independent of demonstration. (The necessity of this is obvious; for since we must know the prior premisses from which the demonstration is drawn, and since the regress must end in immediate truths, those truths must be indemonstrable.) Such, then, is our doctrine, and in addition we maintain that besides scientific knowledge there is its originative source which enables us to recognize the definitions.
cf. also St. Thomas Aquinas's Commentary on Aristotle's Metaphysics IV l. 6 [¶607] for a conciser resolution of the regress problem
Aristotle's conclusion is that, analogous to Gödel, there are truths which cannot be demonstrated.
For example, there are laws of reasoning that are true but cannot be proven to be true, like the principle of non-contradiction, which is the "first indemonstrable principle" (Summa Theologica I-II q. 94 a. 2 c.):
quoted here
[A] certain order is to be found in those things that are apprehended universally. For that which, before aught else, falls under apprehension, is "being," the notion of which is included in all things whatsoever a man apprehends. Wherefore the first indemonstrable principle is that "the same thing cannot be affirmed and denied at the same time," which is based on the notion of "being" and "not-being": and on this principle all others are based, as is stated in Metaph. iv, text. 9.
Is the regress problem a problem in other, non-Aristotelian logics?